admin管理员组文章数量:1642341
题意:一段路上,给出n个慢跑者跑步的区间,给出k,要求让每个慢跑者都能看到k个广告,区间都是整数操作,也就是说一个广告只能放在一个整数上,求最小贴的广告数。
分析:贴小广告的也好辛苦啊(大雾)。
注意如果区间长度小于k的话贴满了就行。
这就是区间选点问题的变形题。排序后从每个区间后面选起就行了。
代码:
/*
* Author: illuz <iilluzen[at]gmail>
* Blog: http://blog.csdn/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;
}
版权声明:本文标题:UVA 10148 Advertisement 贴广告的艺术 贪心 区间选点 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1729327854a1195993.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论