最少拦截系统

 1 #include<stdio.h>
 2 #define INF 0x7ffffff
 3 #define MAXN 10000
 4 int dp[MAXN];                 //dp[i]代表第i个拦截系统当前拦截的高度
 5 int main()
 6 {
 7     int n,x,i,res,flag;        //res拦截系统个数  flag标记是否可以拦截
 8     int minh;       //用来找离要拦截导弹最近的拦截系统
 9     while(scanf("%d",&n)!=EOF)
10     {
11         res=0;
12         while(n--)
13         {
14             scanf("%d",&x);
15             flag=0;       //flag=0为不能拦截
16             minh=INF;      //每次循环都更新
17             int tempi;     //tempi指向发动拦截的拦截系统           
18             for(i=0;i<res;i++)       //res为拦截系统个数，依次查询
19             {
20                 if(x<=dp[i]&&minh>dp[i]-x)     //minh用来比较res个拦截系统 哪个拦截高度离要拦截的导弹更近
21                 {                                //找到最近的后用tempi标记那个，并更新dp[tempi]
22                     minh=dp[i]-x;    
23                     //dp[i]=x;
24                     tempi=i;
25                     flag=1;      //拦截成功
26                 }    
27             }
28             if(flag==0)        //增加拦截系统个数并更新最新拦截系统高度
29             {
30                 dp[res]=x;
31                 res++;
32             }        
33             else dp[tempi]=x;        //更新先前拦截系统高度
34         }
35         printf("%d\n",res);    
36     }    
37     return 0;
38 }