当先锋百科网

首页 1 2 3 4 5 6 7

最少拦截系统（贪心） SDUT

最少拦截系统

Time Limit: 1000 ms Memory Limit: 65536 KiB

Submit Statistic

Problem Description

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

怎么办呢?多搞几套系统呗!你说说倒蛮容易,成本呢?成本是个大问题啊.所以俺就到这里来求救了,请帮助计算一下最少需要多少套拦截系统.

Input

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

Output

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

Sample Input

8 389 207 155 300 299 170 158 65

Sample Output

2

Hint

hdoj1275

 

方法一：因为没有说明导弹的数目，所以系统数的数组需要创建一个足够大的。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int a[10005];
int main()
{
    int n, i, x, count;
    memset(a, 0, sizeof(a));
    while(~scanf("%d", &n))
    {
        count = 0;
        while(n--)
        {
            scanf("%d", &x);
            for(i = 0; i <= count; i++)
            {
                if(a[i] >= x)
                {
                    a[i] = x;
                    break;
                }
            }
            if(a[count] < x)
            {
                count++;
                a[count] = x;
            }
        }
        printf("%d\n", count);
    }
    return 0;
}

方法二：因为不知道导弹的数目，所以用链表写也可以。 

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node
{
    int data;
    struct node *next;
};
struct node * sequence_Linked_List();
void search_change(struct node *, int);
void free_Linked_List(struct node *);
int count = 0;
int main()
{
    int n, h;
    struct node *head;
    head = sequence_Linked_List();///链表不重置的话就需要清空结点
    while(~scanf("%d", &n))///否则就把建立链表这句话写在while里面
    {                  ///但是每组数据都会重新建立链表，耗费大量内存
        count = 0;/// count 定义为全局变量时要记得每次输入一组新数据时
        while(n--)///要重置！！！因为这个出了很多次错误了！
        {
            scanf("%d", &h);
            search_change(head, h);
        }
        printf("%d\n", count);
        free_Linked_List(head);
    }
    return 0;
}
struct node * sequence_Linked_List()
{
    struct node *head;
    head = (struct node *)malloc(sizeof(struct node));
    head->data = -1;///因为此题下方代码需要用到head->data进行比较
    head->next = NULL;///所以此处需要赋值
    return head;
};
void search_change(struct node *head, int n)
{///查找已有系统是否能拦截导弹，并作出处理
    struct node *tail;
    tail = head;
    while(tail)///当 tail = NULL 时结束循环
    {
        if(tail->data >= n)
        {/**从链表头向后遍历，如果找到合适的结点则直接改变数据，
因为每次都是从前往后遍历，没有大于 n 的结点数据时才会建立新结点，
所以在前面的结点的数据一直都是比在后面的结点的数据小的，从前往后遍历
的过程就是找大于 n 的最小数据**/
            tail->data = n;
            return;
        }
        else if(tail->next == NULL)
        {///当遍历到链表尾结点仍没有合适结点时，建立新结点并存放数据
            struct node *p;
            p = (struct node *)malloc(sizeof(struct node));
            p->next = NULL;
            p->data = n;
            tail->next = p;
            count++;
            return;
        }
        if(tail)  tail = tail->next;///每次循环后指针后移
    }
}
void free_Linked_List(struct node *head)
{///释放每一组数据分配的内存
    struct node *p;
    head->data = 0;
    p = head->next;
    while(p)
    {
        head->next = p->next;
        free(p);
        p = head->next;
    }
}