admin管理员组文章数量:1642338
题目:uva10148Advertisement(区间选点)
题目大意:给出n个慢跑选手的慢跑区间,要求每个选手的区间至少要由k个广告,但是如果这个选手的慢跑区间长度放不下K个广告的话(特殊区间),那么就将这个选手的区间内都放满广告就可以了。问要满足上诉的要求,最少需要多少数量的广告,并且要找广告编号从小到大输出。
解题思路:区间选点问题。先将这些区间【a,b】按照b从小到大排序。如果b相同的话就按照a从大到小排序,这样保证前面的区间比后面的区间要小。每次选点的后都选靠近边界的点。这里要注意的是这里是要选K个点。但是这个区间内的可能会已经被前面的区间选了。所以这里要判断一下,这些点有没有被选。还需要判断这个区间是否是特殊的区间。
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1005;
const int M = 20005;
int k, n;
int visit[M]; //标记点选择状态
struct jogger {
int a, b;
}jo[N];
int cmp (const jogger &a, const jogger &b) {
if (a.b == b.b)
return a.a > b.a;
return a.b < b.b;
}
int solve () {
int count = 0;
int s = -M;
int c;
memset (visit, 0, sizeof (visit));
for (int i = 0; i < n; i++) {
if (jo[i].a > s) { //后一个区间和前一个区间没有重合
// printf ("%d\n", jo[i].b - jo[i].a + 1);
if (jo[i].b - jo[i].a + 1 <= k) { //特殊的区间
for (int j = jo[i].a; j <= jo[i].b; j++)
visit[j + 10000] = 1;
count += jo[i].b - jo[i].a + 1;
} else {
// printf ("----\n");
for (int j = jo[i].b; j > jo[i].b - k; j--)
visit[j + 10000] = 1;
count += k;
}
s = jo[i].b;
} else {
c = 0; //由重合的话,需要统计一下这个区间已将选择的点的个数。
for (int j = jo[i].a; j <= s; j++)
if (visit[j + 10000])
c++;
if (jo[i].b - jo[i].a + 1 <= k) { //特殊的区间
if (c >= jo[i].b - jo[i].a + 1)
continue;
for (int j = jo[i].b; j >= jo[i].a; j--) {
if (visit[j + 10000])
continue;
visit[j + 10000] = 1;
count++;
}
s = jo[i].b;
} else {
if (c >= k)
continue;
int m = 0;
for (int j = jo[i].b; j >= jo[i].a; j--) {
if (m + c == k)
break;
if (visit[j + 10000])
continue;
visit[j + 10000] = 1;
count++;
m++;
}
s = jo[i].b;
}
}
}
return count;
}
int main () {
int t;
int a, b;
scanf ("%d", &t);
while (t--) {
scanf ("%d%d", &k, &n);
for (int i = 0; i < n; i++) {
scanf ("%d%d", &a, &b);
if (a < b) {
jo[i].a = a;
jo[i].b = b;
} else {
jo[i].a = b;
jo[i].b = a;
}
}
sort (jo, jo + n, cmp);
int count = solve();
printf ("%d\n", count);
for (int i = 0; i < M; i++)
if (visit[i])
printf ("%d\n", i - 10000);
if (t)
printf ("\n");
}
return 0;
}
本文标签: 区间选点uva10148Advertisement
版权声明:本文标题:uva10148Advertisement(区间选点) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/xitong/1729328052a1196017.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论