抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

总时间限制: 1000ms 内存限制: 262144kB

描述

Freda 报名参加了学校的越野跑。越野跑共有 N 人参加,在一条笔直的道路上进行。这 N 个人在起点处站成一列,相邻两个人之间保持一定的间距。比赛开始后,这 N 个人同时沿着道路向相同的方向跑去。换句话说,这 N 个人可以看作 x 轴上的 N 个点,在比赛开始后,它们同时向 x 轴正方向移动。
假设越野跑的距离足够远,这 N 个人的速度各不相同且保持匀速运动,那么会有多少对参赛者之间发生 “赶超” 的事件呢?

输入

第一行 1 个整数 N。
第二行为 N 个非负整数,按从前到后的顺序给出每个人的跑步速度。
对于 50% 的数据,2<=N<=1000。
对于 100% 的数据,2<=N<=100000。

输出

一个整数,表示有多少对参赛者之间发生赶超事件。

样例输入

1
2
5
1 3 10 8 5

样例输出

1
7

提示

我们把这 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;
}