首先，需要说明的是，这道题并非完整的NOIP1999那个原题，而是我们学校教练的精简题，因为贪心的不顾后特性，无法解出最优解，原题需要DP才能解出，而且你谷的bt数据更是需要$O(n\ log\ n)做法才能解出，$O(n^2)$则会TLE。 本蒟蒻不会DP qwq
话不多说先看题：
某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度不大于$30000$的正整数）。计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。
## 输入
n颗依次飞来的高度（$1\le n\le 1000$）
## 输出
要拦截所有导弹最小配备的系统数$k$
## 样例
### 样例输入1
389 207 155 300 299 170 158 65
### 样例输出1
2
## 提示
不断输入，最后停止（直到输入完输入文件中的所有数据）
cpp
while(cin>>h){
//做一些事情
}
while(scanf("%d",&h)!=EOF){
//做一些事情
}
这道题有一种很明显的贪心策略，即：第一次尽量拦截最高的，然后之后的每一次都拦截尽可能高，但是不足上一个的。
对于多个系统的情况，只需要一个变量计数即可，其它变量重置再来规划，为了区分已经拦截和未拦截的导弹，可以将已经拦截的改为某个特定值，拦截直到发现每一个导弹都是特定值。
因为每次都要寻找后面的最大值，所以这种做法的时间复杂度可以大致估计为$O(n)$
请勿尝试使用贪心通过原题，不然您会爆零的！
具体原因上面已说，因为贪心不一定能求出最优解。
相信理解了上面的解析应该就很简单了：
#include <bits/stdc++.h>
using namespace std;
bool p(int ds[],int n){ //判断是否每一个导弹都被拦截，似乎直接for n次会WA，具体原因未知
for(int i=1;i<=n;i++){
if(ds[i]!=-1) return true;
}
return false;
}
int main(){
ios::sync_with_stdio(0);
int ds[114514],maxi,k=1,m=1;
int ccfxxk=1,max=-0x3f3f3f3f,lmax=0x3f3f3f3f; //ccfxxk OI日常发情(bushi
while(cin>>ds[ccfxxk]) ccfxxk++; //简单的重复输入直到EOF，并记录个数
while(p(ds,ccfxxk)){ //一直拦截到全部都没了为止
if(m>ccfxxk){ //m是记录当前拦截到了第几个,若>n则本套系统已爆,归零换下一个
m=1;
lmax=0x3f3f3f3f; //上一个导弹的高度
max=-0x3f3f3f3f; //本导弹高度
k++; //记录系统个数
}
for(int i=m;i<=ccfxxk;i++){
if(ds[i]>max&&ds[i]<=lmax){ //这里的条件是<上一个且尽可能大
max=ds[i];
maxi=i;
}
}
ds[maxi]=-1; //记录-1以防后面的系统误判,但是不需要特判,因为正常的数据是比-1大的
m=maxi+1;
lmax=max;
max=-0x3f3f3f3f;
}
cout<<k; //最后输出就行力
return 0;
}此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。