zoj3197 Google Book 贪心算法

#include <stdio.h>
#define MAX 5050

int main() {
    int n, i, j, k, x, y, count, len;
    int a[MAX] = {0}, b[MAX] = {0};
    //a[i]表示区间[i,a[i]]中的右端点
    //b[i]记录a[1]-a[i]中的最大值，递归关系b[i]=max(b[i-1],a[i]);b[1]=a[1];
    // freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &len);
        //记住每一次数组都得清零
        for (j = 0; j < MAX; j++) {
            a[j] = 0;//之前，这里用了memset(a,0,sizeof(int));上交时却wa,忘了*n了
        }
        //对于同一左端点的区间，只记录最大的区间
        for (j = 1; j <= len; j++) {
            scanf("%d %d", &x, &y);
            if (a[x] < y) {
                a[x] = y;
            }
        }
        //b[i]记录a[1]－a[i]中的最大值
        for (b[1] = a[1], k = 2; k <= len; k++) {
            if (b[k - 1] > a[k]) {
                b[k] = b[k - 1];
            } else {
                b[k] = a[k];
            }
        }
        //合并区间，并且记数
        for (count = 0, y = 1; y <= len; count++) {
            y = b[y] + 1;
        }
        printf("%d\n", count);
    }
    return 1;
}