首页 › 题库 › C/C++编程考级 › C/C++编程八级 › 简答题
简答题 偏难
#7467

Freda的越野跑(2024.3八级) Freda报名参加了学校的越野跑。越野跑共有N人参加,在一条笔直的道路上进行。这N个人在起点处站成一列,相邻两个人之间保…

Freda的越野跑(2024.3八级)

Freda报名参加了学校的越野跑。越野跑共有N人参加,在一条笔直的道路上进行。这N个人在起点处站成一列,相邻两个人之间保持一定的间距。比赛开始后,这N个人同时沿着道路向相同的方向跑去。换句话说,这N个人可以看作x轴上的N个点,在比赛开始后,它们同时向x轴正方向移动。

假设越野跑的距离足够远,这N个人的速度各不相同且保持匀速运动,那么会有多少对参赛者之间发生“赶超”的事件呢?

时间限制:1000

内存限制:262144

输入

第一行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之间不会发生赶超,因为速度快的起跑时就在前边。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include &lt;iostream&gt; #define N 100002 int a[N] = {0}, t[N] = {0}; long long c = 0; void merge(int l, int m, int r) {   int i = l, j = m + 1, k = l;   while (i &lt;= m &amp;&amp; j &lt;= r)     if (a[i] &gt; a[j])       t[k++] = a[i++];     else {       t[k++] = a[j++];       c += 1 + m - i;     }   while (i &lt;= m)     t[k++] = a[i++];   while (j &lt;= r)     t[k++] = a[j++];   for (i = l; i &lt;= r; ++i)     a[i] = t[i]; } void divide(int l, int r) {   int m;   if (r &gt; l) {     m = (r + l) / 2;     divide(l, m);     divide(m + 1, r);     merge(l, m, r);   } } int main() {   int n, i = 0;   std::cin &gt;&gt; n;   while (i &lt; n)     std::cin &gt;&gt; a[i++];   divide(0, n - 1);   std::cout &lt;&lt; c; }</pre>
这道题暂未补解析。