信息学奥赛一本通T1322-拦截导弹问题(c++ 贪心解法)

解题思路:

注意事项:

参考代码:

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<bits/stdc++.h>
using namespace std;
int n=1;
int intercept[1001],m[1001];
int main()
{
    while(scanf("%d",&m[n])==1)
	{ 
	    // if(m[n]==0) break;
		 n++;
	}
    int temp=-1,chaju=INT_MAX;
    int flag=0,k=1;
    intercept[1]=m[1];
    for(int i=2;i<=n;i++)
    {
    	flag=0;
		for(int j=1;j<=k;j++)
		{
			int t;
			t=intercept[j]-m[i];
			//cout<<t<<' ';
			if(intercept[j]>m[i]&&t<chaju) 
			{
				//cout<<"执行次数"<<endl;
				temp=j;flag=1;chaju=t;
			}
		}
		if(flag==1) {intercept[temp]=m[i];}
		else if(flag==0){k+=1;intercept[k]=m[i];}
	    chaju=INT_MAX;
	  //  cout<<intercept[k]<<endl;;
	}
	cout<<k<<endl;
	return 0;
}