10.导弹拦截

[NOIP1999 普及组] 导弹拦截 - 洛谷

导弹拦截3_哔哩哔哩_bilibili 

---

解题思路：

1.输入的若干个整数为导弹依次发射的高度，因为系统拦截导弹的高度是依次递减的，所要求的数量本质上是在问有多少个递减的高度，如果倒过来就是求最长上升子序列的问题（注意，相邻的两个数字相等也可以，因为是不上升子序列）

2.求最长上升子序列的解法有朴素解法O（N^2）和贪心二分策略解法O（N*logN），在本专栏第九题，在此不再赘述。

3.接下来看第二问，问至少需要多少个系统能拦截所有的导弹，受制于第一问的影响，很容易得出求出一个最长不上升子序列然后标记已被导弹拦截，然后求剩下的导弹的最长不上升子序列，但是这种做法是错误的！

举个例子：7  5  4  1  6  3  2，这七个导弹中，第一轮扫掉了7 5 4 3 2，第二轮扫1，第三轮扫6，需要三个系统，但是7 5 4 1 可以用一个系统，6 3 2也同样用一个系统即可，答案为2

所以这里不能用动态规划，应该用贪心的策略来解

4.可以设置一个ans数组，来标记每个系统拦截完导弹后高度，后续的导弹在已有的系统中寻找，如果没有满足的系统，则需要再开辟一个系统，如果有的话，应该选取哪一个呢？应该选取差值最小的，这样，别的系统可以空出更多的空间来容纳高度更高一点的！

举个例子：第一个系统的目前导弹拦截高度为158  第二个为155，现在飞来的导弹高度为65，则应该用第二个拦截，这样后续飞来157高度的就可以利用第一个系统拦截，不然的话，就得又开辟一个系统！

5.最后输出ans数组的有效长度即可，为系统的个数

---

代码实现：O（N^2） 

---

#include
using namespace std;
int a[2010],dp[2010],ans[2010];
int main()
{
	int n,num=0;
	while(cin>>n)
	{
		a[++num]=n;
	}//输入数据
	
	for(int i=1;i<=num/2;i++)
	{
		swap(a[i],a[num-i+1]); 
	}//头尾交换，便于求解上升子序列 
	
	for(int i=1;i<=num;i++)
	dp[i]=1;//初始化为1，因为本身都是一个单调递增的序列 
	
	for(int i=2;i<=num;i++)//从第二项开始遍历 
	{
		for(int j=1;j//枚举第i项前面的数字 
		{
			if(a[i]>=a[j])//如果可以以i结尾 
			{
				dp[i]=max(dp[i],dp[j]+1);//状态转移方程 
			}
		}
	}
	
	int max=0;
	for(int i=1;i<=num;i++)//遍历以每一个数字结尾的上升子序列数 
	if(dp[i]>max)
	max=dp[i];//求最大值
	 
	cout<
	
	int len=1;
	for(int i=1;i<=num/2;i++)
	{
		swap(a[i],a[num-i+1]); 
	}//头尾交换，便于求解系统的个数 
	
	ans[1]=a[1];//初始化第一个被拦截的导弹高度 
	for(int i=2;i<=num;i++)//从第二个导弹的高度开始判断 
	{
		bool flag=0;
		int min=99999999,res;
		for(int j=1;j<=len;j++)//在已有的系统中进行寻找 
		{
			if(a[i]<=ans[j])//如果有这个系统可以拦截这枚导弹 
			{
				flag=1;//打标记 
				if((ans[j]-a[i])//找差值最小的编号 
				{
					min=(ans[j]-a[i]);
					res=j;//记录该系统的编号 
				}
			}
		}
		if(flag==1)//如果可以拦截这枚导弹 
		ans[res]=a[i];//将这枚导弹放在离他高度最近的那个系统上 
		else//如果拦截不了 
		ans[++len]=a[i];//开辟一个新的系统，当前高度为a[i] 
	}
	cout<//长度即为系统的数量 
	return 0;
}

---

代码实现：O（N*logN）

---

#include
using namespace std;
int a[100010],dp[100010],ans[100010];
int main()
{
	int n,num=0;
	while(cin>>n)
	{
		a[++num]=n;
	}//输入数据
	
	for(int i=1;i<=num/2;i++)
	{
		swap(a[i],a[num-i+1]); 
	}//头尾交换，便于求解上升子序列 
	
	
	int len=1;
	dp[1]=a[1];//将第一个数字设置为上升长度1 
	for(int i=2;i<=num;i++)//从第二项开始遍历 
	{
		
		if(a[i]>=dp[len])//如果当前项大于等于此时的上升序列最后一个数 
		dp[++len]=a[i]; //长度加1，表示又多了一个 
		else
		{
			int high=len,low=0,mid;//否则设置二分查找的区间 
			
			while(low
			{
				mid=(low+high)/2;
				
				if(dp[mid]>a[i]) 
				high=mid;
				else
				low=mid+1;
			}
			
			dp[low]=min(dp[low],a[i]);//更新末尾数字 
		} 
	}
	cout<
	
	len=1;
	for(int i=1;i<=num/2;i++)
	{
		swap(a[i],a[num-i+1]); 
	}//头尾交换，便于求解系统的个数 
	
	ans[1]=a[1];//初始化第一个被拦截的导弹高度 
	for(int i=2;i<=num;i++)//从第二个导弹的高度开始判断 
	{
		bool flag=0;
		int min=99999999,res;
		for(int j=1;j<=len;j++)//在已有的系统中进行寻找 
		{
			if(a[i]<=ans[j])//如果有这个系统可以拦截这枚导弹 
			{
				flag=1;//打标记 
				if((ans[j]-a[i])//找差值最小的编号 
				{
					min=(ans[j]-a[i]);
					res=j;//记录该系统的编号 
				}
			}
		}
		if(flag==1)//如果可以拦截这枚导弹 
		ans[res]=a[i];//将这枚导弹放在离他高度最近的那个系统上 
		else//如果拦截不了 
		ans[++len]=a[i];//开辟一个新的系统，当前高度为a[i] 
	}
	cout<//长度即为系统的数量 
	return 0;
}