1322：【例6.4】拦截导弹问题(Noip1999)

 1 #include<iostream>
 2 using namespace std;
 3 const int N=1005;
 4 int main(){
 5     int t,r=0,k[N];
 6     while(cin>>t){
 7         //遍历已有的拦截系统，选择代价最小的进行拦截，实在拦截不了就再添加一个拦截系统
 8         int mi=30*N,s;
 9         for(int i=0;i<r;i++){
10             if(t<=k[i]){
11                 if(mi>k[i]-t){
12                     mi=k[i]-t;
13                     s=i;
14                 }
15             }
16         }
17         if(mi<30*N)k[s]=t;
18         else k[r++]=t;
19     }
20     cout<<r;
21     return 0;
22 }