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

题意：一段路上，给出n个慢跑者跑步的区间，给出k，要求让每个慢跑者都能看到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;
}