首先，需要说明的是，这道题并非完整的NOIP1999那个原题，而是我们学校教练的精简题，因为贪心的不顾后特性，无法解出最优解，原题需要DP才能解出，而且你谷的bt数据更是需要O(n log n)做法才能解出，O(n\ log\ n)做法才能解出，O(n^2)$则会TLE。 本蒟蒻不会DP qwq

题面

话不多说先看题：

查看题面

某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度不大于3000030000的正整数）。计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。

输入

n颗依次飞来的高度（1≤n≤10001\le n\le 1000）

输出

要拦截所有导弹最小配备的系统数kk

样例

样例输入1

1
389 207 155 300 299 170 158 65

样例输出1

1
2

提示

不断输入，最后停止（直到输入完输入文件中的所有数据）

1
2
3
4
5
6
7
8
9
10
11
12
while(cin>>h){

//做一些事情

}


while(scanf("%d",&h)!=EOF){

//做一些事情

}

解析

这道题有一种很明显的贪心策略，即：第一次尽量拦截最高的，然后之后的每一次都拦截尽可能高，但是不足上一个的。

对于多个系统的情况，只需要一个变量计数即可，其它变量重置再来规划，为了区分已经拦截和未拦截的导弹，可以将已经拦截的改为某个特定值，拦截直到发现每一个导弹都是特定值。

因为每次都要寻找后面的最大值，所以这种做法的时间复杂度可以大致估计为O(n)O(n)

请勿尝试使用贪心通过原题，不然您会爆零的！

具体原因上面已说，因为贪心不一定能求出最优解。

代码

相信理解了上面的解析应该就很简单了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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;
}