【jzyz-p1136】超车

这道题从看到它开始到做出来,已经过了快两周【因为第一次思路完全跑偏写的是暴力模拟想水过】

题意是这样的:

jzabc除了对多米诺骨牌感兴趣外,对赛车也很感兴趣。上个周末他观看了一场赛车比赛。他总是能想出许多稀奇的问题。某一时刻,他看到有n辆车(总是匀速行驶)在同一直线上,并且处在一个无限长度的直道上,而且n辆车有严格的先后之分。他通过特殊的器材测出了每一辆车的速度。那么问题出现了,如果有两辆车A车和B车,A车在B车的后面,并且A车的速度比B车的快,那么经过一段时间后,A车一定会超过B车。我们称之为一次超车。那么他想请你帮忙计算超车总数。我们记车道起点的坐标为0。没有两辆车的坐标相同。

输入:

第一行,一个数n,车辆总数。

第二行至第n+1行,为n辆车的信息
每行有两个正整数x,y,x和y之间有一个空格
x为车的坐标,y为车的速度
$0<x, y<=1000000000$

输出:

超车总数【逆序对个数】

先说说我第一次没看书理解的题意:开一个结构体,按坐标从小到大sort记录位次,然后sort按速度排序,用总数减去每次的位次,然后累加。后来发现如果速度大的在前次大的数不可能超过,而记录它之前的车总数-1不管从时间上还是从策略上都很难满足【已经按速度排序不可能从1循环到这辆车】。

然后从书上看到了这道题,本来准备看代码试一下,然后yyx同学告诉我这个代码完全是个bug,我就信了,根本不敢打,事实上证明书上的代码是正确的orz

事实证明自己努力想一些东西还是好的。解题思路大概就是将序列分开然后排序,然后把两个排过的合并。因为两边的序列有序,那么在一边选取的数和另一边比较,前面的数肯定全

都是逆序的。将排序和统计同时进行,不会影响最终答案。

ps:注意统计数据量…会爆掉int

下面放代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
long long ans=0;
struct qaq
{
int x;
int y;
};
qaq car[300100];
int c[300100];
int a[300100];

bool mycmp(qaq a,qaq b)
{return a.x<b.x;}

void init()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d",&car[i].x,&car[i].y);
sort(car+1,car+1+n,mycmp);
for(int i=1;i<=n;i++)
a[i]=car[i].y;
//for(int i=1;i<=n;i++) cout<<a[i]<<' '; cout<<endl<<"----------------";
}

void work(int l,int r)
{
int i,j,mid,temp;

if(l+1<r)
{
mid=(l+r)/2;
work(l,mid-1);
work(mid,r);
temp=l;
for(i=l,j=mid;(i<=mid-1)&&(j<=r);)
{
if(a[i]>a[j])
{
c[temp++]=a[j++];
ans+=mid-i;
}
else c[temp++]=a[i++];
}

if(j<=r)
{
for(;j<=r;j++) c[temp++]=a[j];
}
else
{
for(;i<=mid-1;i++) c[temp++]=a[i];
}

for(int i=l;i<=r;i++) a[i]=c[i];
}

else
{
if(l+1==r)
{
if(a[l]>a[r])
{
int tt=a[r];
a[r]=a[l];
a[l]=tt;
ans++;
}
}
}
}


int main()
{
init();
work(1,n);
cout<<ans<<endl;
return 0;
}