A32864. Freda的越野跑Freda报名参加了学校的越野跑。越野跑共有N人参加，在一条笔直的道路上进行。这N个人在起点处站成一列，相邻两个人之间保持一定的间距。比赛开始后，这N个人同时沿着道路向相同的方向跑去。换句话说，这N个人可以看作x轴上的N个点，在比赛开始后，它们同时向x轴正方向移动。假设越野跑的距离足够远，这N个人的速度各不相同且保持匀速运动，那么会有多少对参赛者之间发生“赶超”的事件呢？输入第…
填空题
困难
知识点
题目描述
Freda的越野跑
Freda报名参加了学校的越野跑。越野跑共有N人参加，在一条笔直的道路上进行。这N个人在起点处站成一列，相邻两个人之间保持一定的间距。比赛开始后，这N个人同时沿着道路向相同的方向跑去。换句话说，这N个人可以看作x轴上的N个点，在比赛开始后，它们同时向x轴正方向移动。
假设越野跑的距离足够远，这N个人的速度各不相同且保持匀速运动，那么会有多少对参赛者之间发生“赶超”的事件呢？
输入
第一行1个整数N。
第二行为N 个非负整数，按从前到后的顺序给出每个人的跑步速度。
对于50%的数据，2<=N<=1000。 对于100%的数据，2<=N<=100000。
输出
一个整数，表示有多少对参赛者之间发生赶超事件。
样例输入
5
1 3 10 8 5
样例输出
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之间不会发生赶超，因为速度快的起跑时就在前边。
参考答案
#include <iostream>
using namespace std;
int a[100001];
int ta[100001];
long long int ans = 0;
void merge(int left, int right, int middle)
{
int i, j, index1, index2;
for (j = left; j <= right; ++j)
ta[j] = a[j];
index1 = left;
index2 = middle + 1;
i = left;
while (index1 <= middle && index2 <= right)
{
if (ta[index1] >= ta[index2])
{
a[i] = ta[index1];
++i;
++index1;
}
else
{
a[i] = ta[index2];
ans += middle - index1 + 1; //这个右子列元素超过了左子列中剩余的元素
++i;
++index2;
}
}
while (index1 <= middle)
{
a[i] = ta[index1];
++i;
++index1;
}
while (index2 <= right)
{
a[i] = ta[index2];
++i;
++index2;
}
}
void mergesort(int left, int right)
{
int middle;
if (left < right)
{
middle = (left + right) / 2;
mergesort(left, middle);
mergesort(middle + 1, right);
merge(left, right, middle);
}
}
int main()
{
int n;
cin >> n;
for (int i = 0; i < n; ++i)
{
scanf("%d", &a[i]);
}
mergesort(0, n - 1);
cout << ans;
//system("pause");
return 0;
}
上一题
下一题