UVA 10148 Advertisement 貼廣告的藝術 貪心 區間選點

分析：貼小廣告的也好辛苦啊（大霧）。 注意如果區間長度小於k的話貼滿了就行。 這就是區間選點問題的變形題。排序後從每個區間後面選起就行了。 代碼：

題意：一段路上，給出n個慢跑者跑步的區間，給出k，要求讓每個慢跑者都能看到k個廣告，區間都是整數操作，也就是說一個廣告只能放在一個整數上，求最小貼的廣告數。

 /* 
 *   Author:        illuz <iilluzen[at]gmail.com> 
 *   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 <cstdio>  
#include <cstring>  
#include <algorithm>  
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;  
}