贪心—最少拦截系统

刺骨的言语ヽ痛彻心扉 2022-07-11 09:22 132阅读 0赞

最少拦截系统  
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description  
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度.某天,雷达捕捉到敌国的导弹来袭.由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹.  
怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

Input  
输入若干组数据.每组数据包括:导弹总个数(正整数),导弹依此飞来的高度(雷达给出的高度数据是不大于30000的正整数,用空格分隔)

Output  
对应每组数据输出拦截所有导弹最少要配备多少套这种导弹拦截系统.

Example Input  
8 389 207 155 300 299 170 158 65

Example Output  
2

Hint  
hdoj1275

Author

以下为accepted代码

#include <stdio.h>
    #define MAXN 30004
    int main()
    {
        int a[MAXN];
        int n, i, j, maxh, count;
        while(scanf("%d", &n) != EOF)
        {
            count = 0;
            for(i = 0; i < n; i++)
            {
                scanf("%d", &a[i]);
            }
            //考虑导弹拦截的先后顺序与相距高度
            for(i = 0; i < n; i++)
            {
                maxh = a[i];
                if(maxh != 0)
                {
                    for(j = i+1; j < n; j++)
                    {
                        if(a[j] <= maxh && a[j] != 0)
                        {
                            maxh = a[j];
                            a[j] = 0;
                        }
                    }
                    count++;
                }
            }
            printf("%d\n", count);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Accepted
    Take time: 0ms
    Take Memory: 120KB
    Submit time: 2017-01-22 19:54:49
    ****************************************************/

以下为wrong answer代码

#include <stdio.h>
    #define MAXN 30004
    int main()
    {
        int a[MAXN];
        int n, i, count;
        while(scanf("%d", &n) != EOF)
        {
            for(i = 0; i < n; i++)
            {
                scanf("%d", &a[i]);
            }
            count = 1;
            for(i = 0; i < n-1; i++)
            {
                if(a[i] < a[i+1])
                {
                    count++;
                }
            }
            if(n != 0)
                printf("%d\n", count);
            else if(n == 0)
                printf("%d\n", count-1);
        }
        return 0;
    }
    
    
    /***************************************************
    User name: jk160630
    Result: Wrong Answer
    Take time: 0ms
    Take Memory: 112KB
    Submit time: 2017-01-22 19:21:43
    ****************************************************/

introspection: 1、心态不稳、理解片面