題目：http://acm.fzu.edu.cn/problem.php?pid=1021

分析：被超車：起始比“我”落后，速度卻比“我”快。由于起步位置按從小到大排序，所以在“我”之前讀入的飛船一定比我落后，那只用找速度比我快的。那是不是不斷地遍歷之前的，比較速度大小呢？肯定超時！

這里提供了一種新的思路（感覺我一輩子也想不到了）：速度v<100，定義數(shù)組v[100],v[i]表示速度為i的飛船的個數(shù)（隨著輸入，不斷變化），當前的車被超次數(shù)：v[i+1],v[i+2],v[i+3]......v[99]（此時的v不包含當前飛船之后的飛船）。

代碼<c語言>：

1 #include<stdio.h> 2 int main() 3 { 4 int v[100],sum,n,i,j,a,b; 5 while(~scanf("%d",&n)&&n) 6 { 7 //初始化 8 sum=0; 9 for(i=0; i<100; i++) //比b速度大的,當前數(shù)組 10 v[i]=0; 11 for(i=0; i<n; i++) 12 { 13 scanf("%d %d",&a,&b); 14 v[b]++; 15 for(j=b+1; j<100; j++) //比b速度大的,當前數(shù)組只記錄了該車之前的數(shù)據(jù) 16 { 17 sum=sum+v[j]; 18 if(sum>=1000000)//取模 19 sum%=1000000; 20 } 21 } 22 printf("%d\n",sum); 23 } 24 return 0; 25 }

?

注意：1.sum=sum+v[j];當前數(shù)組v 只記錄了該車之前的數(shù)據(jù)，所以必須一邊輸入，一邊計算“超車”次數(shù)。

2.取模操作的位置：if(sum>=1000000)??sum%=1000000; 應(yīng)該放在for循環(huán)里，本以為都不用取模，因為 飛船個數(shù)<250000,但是n架飛船，最壞會有(n-1)+(n-2)+(n-3)+......+1種”超車“情況，求和的過程中，極有可能超過int范圍，故應(yīng)及時取模。

?

轉(zhuǎn)載于:https://www.cnblogs.com/li-yaoyao/p/9439517.html

總結(jié)

以上是生活随笔為你收集整理的飞船赛——FOJ 1021的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。