贪心算法：拦截导弹问题

本文主要是介绍贪心算法：拦截导弹问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

贪心算法：拦截导弹问题

Time Limit: 1 Sec
Memory Limit: 128 MB
64bit IO Format: %lld

Description

某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。

Input

包含多组测试数据。每组测试数据占一行。第一个正整数为导弹数量n，后面紧接n颗依次飞来的导弹的高度（1≤n≤1000）。

Output

输出要拦截所有导弹最小配备的系统数k。

Sample Input

8
389 207 155 300 299 170 158 65
（这里我改变了题目的数据样式，看的清楚一点）

Sample Output

傻瓜式总结，基本上是从新手踩雷的角度来做的。（我踩了大概一天的雷，春节围绕着一群可爱的小朋友写题）
在这里插入图片描述

首先题目分析

最贴合本身的思维就是按照那组数据的顺序，分出从大到小的几个数组，最后看有几组数组，就意味着我们要最少要有几套系统。
以题目数据为例

389 207 155 300 299 170 158 65

排序

1：389 300 299 170 158 65
2：207 155

所以最少需要两套系统

好的想到这里说明你已经有可能做出来了，
接下来就是一个急转弯。
在这里插入图片描述

目的变成了利用上面的函数找到最长的一组递增数

注意：这组数是可以不连续的。（不信自己试，但是dilworth定理里链的定义我没有细看，也不知道，可能有关系。至于我怎么在没看懂的情况下发现的，归功于wa。）

下面就是逐项比较，用一个数组记录，最后输出最长的递增数的个数。

上代码

#include<iostream>
using namespace std;
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<map>const int N = 1e5+10;
int a[N], d[N], n;int main()
{ios_base::sync_with_stdio(0);while(cin >> n){for(int i=1;i<=n;i++)cin >> a[i];int len = 1;d[1] = a[1];for (int i=2; i<=n; i++){if(d[len] < a[i])d[++len] = a[i];else{int p = lower_bound(d + 1, d + 1 + len, a[i]) - d;d[p] = a[i];}}cout << len << endl;}return 0;
}