UVA 10148 Advertisement 贴广告的艺术 贪心 区间选点

题意：一段路上，给出n个慢跑者跑步的区间，给出k，要求让每个慢跑者都能看到k个广告，区间都是整数操作，也就是说一个广告只能放在一个整数上，求最小贴的广告数。

 /* 
 *   Author:        illuz  
 *   Blog:          http://blog.csdn.net/hcbbt 
 *   File:          uva10148.cpp 
 *   Lauguage:      C/C++ 
 *   Create Date:   2013-09-06 19:58:01 
 *   Descripton:    UVA 10148 Advertisement, 区间选点 
 */  
#include   
#include   
#include   
using namespace std;  
#define rep(i, n) for (int i = 0; i < (n); i++)  
#define repf(i, a, b) for (int i = (a); i <= (b); i++)  
#define mc(a) memset(a, 0, sizeof(a))  
  
const int MAXN = 1001;   
const int T = 10000;  
  
struct P {  
    int lhs, rhs;  
} p[MAXN];  
int k, n, a, b;  
int hash[T * 2 + 2];  
  
bool cmp(P a, P b) {  
    return a.rhs < b.rhs;  
}  
  
int main() {  
    int t;  
    scanf("%d", &t);  
    rep(cas, t) {  
        mc(hash);  
        // input  
        scanf("%d%d", &k, &n);  
        rep(i, n) {  
            scanf("%d%d", &a, &b);  
            if (a > b) p[i].lhs = b + T, p[i].rhs = a + T;  
            else p[i].lhs = a + T, p[i].rhs = b + T;  
        }  
        sort (p, p + n, cmp);  
        // solve  
        int tk, cnt = 0;  
        rep(i, n) {  
            tk = 0;  
            repf(j, p[i].lhs, p[i].rhs)  
                if (hash[j])  
                    tk++;  
            for (int j = p[i].rhs; j >= p[i].lhs && tk < k; j--)  
                if (!hash[j]) {  
                    hash[j]++;  
                    cnt++; tk++;  
                }  
        }  
        if (cas) printf("\n");  
        printf("%d\n", cnt);  
        rep(i, 2 * T + 1) if (hash[i]) printf("%d\n", i - T);  
    }  
    return 0;  
}