总时间限制: 1000ms 内存限制: 262144kB
描述
Freda 报名参加了学校的越野跑。越野跑共有 N 人参加,在一条笔直的道路上进行。这 N 个人在起点处站成一列,相邻两个人之间保持一定的间距。比赛开始后,这 N 个人同时沿着道路向相同的方向跑去。换句话说,这 N 个人可以看作 x 轴上的 N 个点,在比赛开始后,它们同时向 x 轴正方向移动。
假设越野跑的距离足够远,这 N 个人的速度各不相同且保持匀速运动,那么会有多少对参赛者之间发生 “赶超” 的事件呢?
输入
第一行 1 个整数 N。
第二行为 N 个非负整数,按从前到后的顺序给出每个人的跑步速度。
对于 50% 的数据,2<=N<=1000。
对于 100% 的数据,2<=N<=100000。
输出
一个整数,表示有多少对参赛者之间发生赶超事件。
样例输入
样例输出
提示
我们把这 5 个人依次编号为 A,B,C,D,E,速度分别为 1,3,10,8,5。
在跑步过程中:
B,C,D,E 均会超过 A,因为他们的速度都比 A 快;
C,D,E 都会超过 B,因为他们的速度都比 B 快;
C,D,E 之间不会发生赶超,因为速度快的起跑时就在前边。
Code
最开始时候的想法
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 #include <bits/stdc++.h> using namespace std;array<int , 100003> a; long res;void merge (int begin1, int mid, int end1) { array<int , 100003> b, c; int l1 = 0 , l2 = 0 ; for (int i = begin1; i <= mid; ++i) { b[l1++] = a[i]; } for (int i = mid+1 ; i <= end1; ++i) { c[l2++] = a[i]; } int i = 0 , j = 0 , k = begin1; while (j < l2 && i < l1) { if (b[i] >= c[j]) { a[k] = b[i++]; } else { a[k] = c[j++]; res += mid+j-k; } ++k; } while (i < l1) a[k++] = b[i++]; while (j < l2) a[k++] = c[j++]; } void mergesort (int begin1, int end1) { if (begin1 == end1) return ; mergesort (begin1, (begin1+end1)/2 ); mergesort ((begin1+end1)/2 +1 , end1); merge (begin1, (begin1+end1)/2 , end1); } int main () { int N; scanf ("%d" , &N); for (int i = 0 ; i < N; ++i) { scanf ("%d" , &a[i]); } mergesort (0 , N-1 ); printf ("%ld\n" , res); res = 0 ; }