2150拦截导弹问题 简单贪心算法(注释很详细)

//贪心规则:炮弹打过来,让当前高度最低的系统去应对
//如果应对不了,就加一个系统,最后统计系统数

#include<bits/stdc++.h>

int s[1005];//系统system,下标代表第几个系统,数据表示系统当前高度

int h;//炮弹高度height

int n;//记录系统数量

int min;//用于寻找高度最低的系统

int i;

int main()
{
	
	while(scanf("%d",&h) != EOF)
	{
		min = n;//先假设系统n就是高度最低的系统
		//实际上系统n刚刚建立的时候一定是所有系统中高度最高的系统
		//这样假设是为了方便寻找满足高度条件的系统
		for(i = 1; i <= n; i++)
		{
			if(s[i] < s[min]  && s[i] >= h)
			{
				min = i;
			}
		}
		
		if(s[min] >= h)//如果可以拦截的话
		{
			s[min] = h;//高度最低的系统去拦截该导弹,同时该系统的高度更新
		}
		else//如果不能,就要增加系统
		{
			s[++n] = h;//并且设置系统高度为该导弹高度
		}
	}
	printf("%d",n);
	
	return 0;
}