DAY 3 问题 B: 超车

问题 B: 超车
时间限制: 1 Sec 内存限制: 128 MB
提交: 26 解决: 4
[提交][状态]
题目描述
Jzabc对赛车也很感兴趣,在参观车展是,想到这样一个问题,在某时刻,他看到n辆车(总是匀速行驶)在同一直线上,且处于一个无限长的直道上,而且n辆车有严格的先后之分,。他通过特殊的器材测出了每辆车的速度,那么问题出现了,如果有车A和车B,A在B的后面,且A的速度快于B的,那么经过一段时间后,A一定会超过B,我们称之为一次超车。那么他想请你帮忙计算超车总数。我们记车道起点的坐标为0 ,没有两辆车的坐标相同。

输入
第一行,一个数N,表示车辆总数。以下n行为N辆车的信息; 第二行至第N+1行,每行有两个正整数X、Y,X和Y之间有一个空格,其中X为车的坐标,Y为车的速度。 0<=X,Y<=1000000000

输出
一行,超车总数

样例输入
2
5 6
2 8
样例输出
1
提示

对于20%的数据,满足N<=300

对于50%的数据,满足N<=3000

对于100%的数据,满足N<=300000

#include<cstdio> 
#include<algorithm> 
#include<cstring> 
#include <iostream> 
#define mo 100000000 
#define int long long 
using namespace std;   
int n; 
struct NODE{ 
    int x,v; 
}dmf[300005]; 
int t[300005]; 
int tem[300005]; 
inline bool cmp(NODE a,NODE b){ 
    return a.x<b.x; 
} 
int ans=0; 
void gui(int l,int r){ 
    int i=l; 
    int mid=l+r>>1; 
    int j=mid+1; 
    int k=l; 
    while(i<=mid&&j<=r){ 
        if(t[i]>t[j]){ 
            tem[k++]=t[j++]; 
            ans+=mid-i+1; 
        } 
        else{ 
            tem[k++]=t[i++]; 
        } 
    } 
    while(i<=mid) tem[k++]=t[i++]; 
    while(j<=r) tem[k++]=t[j++]; 
    for(int i=l;i<=r;i++) 
     t[i]=tem[i]; 
} 
void work(int l,int r){ 
    if(l<r) 
    { 
        int mid=l+r>>1; 
        work(l,mid); 
        work(mid+1,r); 
        gui(l,r);        
    } 

} 
main(){ 
    scanf("%lld",&n); 
    for(int i=1;i<=n;i++){ 
        scanf("%lld%lld",&dmf[i].x,&dmf[i].v); 
    } 
    sort(dmf+1,dmf+n+1,cmp); 
    for(int i=1;i<=n;i++) t[i]=dmf[i].v; 
    work(1,n); 
    cout<<ans; 
    return 0; 
}

这题没啥用,就是复习下逆序对hiahiahia

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-31 20:32
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
2022-12-22 18:27
天津大学_2023
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议