HDU2037 今年暑假不AC

问题链接：HDU2037 今年暑假不AC。

问题简述：参见上述链接。

问题分析：典型的贪心算法题，分别用C语言和C++语言编写程序。

若干个电视节目，自然要按时间顺序来看。为了看更多的节目，需要尽快看完一个节目再看另外一个节目，多看短节目才能看更多的节目。

程序说明：C语言程序与C++语言程序的差别，只在排序方面，调用的函数与参数不同。

AC的C语言程序如下：

/* HDU2037 今年暑假不AC */

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100

struct node {
    int start;
    int end;
} record[MAXN];

int cmp(const void * a, const void * b)
{
    struct node *x = (struct node *) a;
    struct node *y = (struct node *) b;
    return x->end - y->end;
}

int main(void)
{
    int n, count, lastend, i;

    while(scanf("%d", &n) != EOF) {
        // 判定结束条件
        if(n == 0)
            break;

        // 读入原始数据
        for(i=0; i<n; i++)
            scanf("%d%d", &record[i].start, &record[i].end);

        // 排序：按结束时间排序
        qsort(record, n, sizeof(record[0]), cmp);

        // 贪心法处理：后一个起始时间必须大于或等于前一个终止时间
        count = 0;
        lastend = -1;
        for(i=0; i<n; i++) {
            if(record[i].start >= lastend) {
                count++;
                lastend = record[i].end;
            }
        }

        // 输出结果
        printf("%d
", count);
    }

    return 0;
}

AC的C++语言程序如下：

/* HDU2037 今年暑假不AC */

#include <iostream>
#include <algorithm>

using namespace std;

#define MAXN 100

struct node {
    int start;
    int end;
} record[MAXN];

bool cmp(const node& a, const node& b)
{
    return a.end < b.end;
}

int main()
{
    int n, count, lastend, i;

    for(;;) {
        // 读入n
        cin >> n;

        // 判定结束条件
        if(n == 0)
            break;

        // 读入原始数据
        for(i=0; i<n; i++)
            cin >> record[i].start >> record[i].end;

        // 排序：按结束时间排序
        sort(record, record + n, cmp);

        // 贪心法处理：后一个起始时间必须大于或等于前一个终止时间
        count = 0;
        lastend = -1;
        for(i=0; i<n; i++) {
            if(record[i].start >= lastend) {
                count++;
                lastend = record[i].end;
            }
        }

        // 输出结果
        cout << count << endl;
    }

    return 0;
}