UC知道超车问题请编程高手帮助
来源：百度知道 编辑：UC知道 时间：2024/05/08 21:26:29
赛车比赛中最精彩的部分莫过于超车，假设在赛车比赛中，赛道的长度是无限的，并且
每辆赛车的起始点和速度也各不相同，请你计算出在比赛中超车场面出现的次数。
两辆赛车A和B，初始时A在B的前面，在某一时刻t，如果B在A的前面，那么我们称这是
一次超车。
编程任务：
请你根据每辆赛车的起始点和速度,编程计算出在比赛中可以看到超车场面的总次数。
数据输入：
由文件input.txt给出输入数据。第一行有1个正整数N，表示赛车的总数(0<N<=50000)。
接下来有一行，按赛车的起始点位置从前往后的顺序给出每辆赛车的速度V。(0<V<2^31)
结果输出:
将计算出的超车场面的总次数输出到文件output.txt。
输入示例 输出示例
input.txt output.txt 9
10
19 16 13 18 15 12 17 14 11 10
以上是题目，希望是复杂度为O（n）或O(nlogn)的算法，拜托高手帮助。
每辆赛车的起始点和速度也各不相同，请你计算出在比赛中超车场面出现的次数。
两辆赛车A和B，初始时A在B的前面，在某一时刻t，如果B在A的前面，那么我们称这是
一次超车。
编程任务：
请你根据每辆赛车的起始点和速度,编程计算出在比赛中可以看到超车场面的总次数。
数据输入：
由文件input.txt给出输入数据。第一行有1个正整数N，表示赛车的总数(0<N<=50000)。
接下来有一行，按赛车的起始点位置从前往后的顺序给出每辆赛车的速度V。(0<V<2^31)
结果输出:
将计算出的超车场面的总次数输出到文件output.txt。
输入示例 输出示例
input.txt output.txt 9
10
19 16 13 18 15 12 17 14 11 10
以上是题目，希望是复杂度为O（n）或O(nlogn)的算法，拜托高手帮助。
你可以参考
http://acm.fzu.edu.cn/problem.php?pid=1021
这题
#include <stdio.h>
int main()
{
int N;
while(scanf("%d",&N))
{
if(N==0) break;
int V[100]={0};
int x,v,i;
int sum=0;
for(;N>0;N--)
{
scanf("%d %d",&x,&v);
V[v]+=1;
for(i=v+1;i<100;i++)
{
if(V[i]) sum+=V[i];
if(sum>1000000) sum%=1000000;
}
}
printf("%d\n",sum);
}
return 0;
}
哇，你是牛人，这么专业的问题估计能回答的人不多，只能你自己去想了