本文主要是介绍B_飞船赛，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
B - 飞船赛
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Description
有N个飞船进行比赛，它们的跑道为直线并互相平行。每个飞船的起跑位置均不相同。第i个飞船从起跑线右边Xi处开始向右行驶（Xi各不相同）。比赛开始后，它能在零时间内加速到最大速度Vi并永远保持此速度。比赛没有终点，即会永远进行下去。
你的任务是算出比赛过程中一共有多少次"超车"。
Input
输入数据由多组数据组成。每组数据格式如下：
第一行为一个整数N（1<=N<=250000）。
接下来的N行，每行两个整数Xi (0≤Xi≤10^6)和Vi(0<Vi<100)，描述了一辆飞船的起跑位置和最大速度。
给出的飞船信息按照起跑位置Xi的升序排列，即X1<X2<X3<…<Xn。
最后一组数据N=0，标志输入结束，不需要处理。
第一行为一个整数N（1<=N<=250000）。
接下来的N行，每行两个整数Xi (0≤Xi≤10^6)和Vi(0<Vi<100)，描述了一辆飞船的起跑位置和最大速度。
给出的飞船信息按照起跑位置Xi的升序排列，即X1<X2<X3<…<Xn。
最后一组数据N=0，标志输入结束，不需要处理。
Output
对于每组数据，输出仅一行包含一个整数，即"超车"的次数对1000000的模。
Sample Input
4 0 2 2 1 3 8 6 3 0
Sample Output
2
这是一道很明显的剪枝题，减少循环的次数；
一般人的思路是不断比较，但是根据题目可知很容易超时，所以需要转化思路，从速度出发会减少循环的次数：
#include<stdio.h> #include<string.h> int s[107]; int main() {int n;while(scanf("%d",&n),n){int a,b;__int64 count=0;memset(s,0,sizeof(s));for(int i=0;i<n;i++){scanf("%d%d",&a,&b);s[b]++;for(int j=b+1;j<100;j++){count+=s[j];}}printf("%d\n",count%1000000);}return 0; }
这篇关于B_飞船赛的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
