题意:admin管理员组文章数量:1642338
这题是区间选点问题的改版。
大概翻译一下:
一广告商想在一条街上贴小广告,于是他随机采访了n个慢跑者,得到了这些人每天经过这条路的起始位置和结束位置,现在广告商要让,这些人经过的路上至少贴上k个广告,如果距离比k小,则全贴广告。
现在要求你求出最少贴多少的广告,才能满足上述要求,并把贴广告的点,全部输出。
两个样例直接输出一个空行。
解析:
从第一个区间遍历到最后一个区间
开一个vis[20000]数组进行标记,每次先遍历该区间,查看是否有k个点,如果没有k个点,则将该区间从后往前进行标记直到满足k个点为止。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10000;
const int MAX = 20010;
const int INF = 0x3f3f3f3f;
struct Segment {
int l,r;
}s[N];
int vis[MAX];
int save[MAX];
int k,n;
bool cmp(Segment a,Segment b) {
if(a.r != b.r) {
return a.r < b.r;
}
return a.l < b.l;
}
int main() {
int t;
scanf("%d",&t);
while(t--) {
scanf("%d%d",&k,&n);
for(int i = 0; i < n; i++) {
scanf("%d%d",&s[i].l,&s[i].r);
if(s[i].l > s[i].r) {
swap(s[i].l,s[i].r);
}
}
sort(s,s+n,cmp);
memset(vis,0,sizeof(vis));
int sum = 0;
for(int i = 0; i < n; i++) {
int cnt = 0;
for(int j = s[i].l; j <= s[i].r; j++) {
if(vis[j+N]) {
cnt++;
}
}
if(cnt >= k) {
continue;
}
for(int j = s[i].r; j >= s[i].l && cnt < k; j--) {
if(!vis[j+N]) {
vis[j+N] = true;
save[sum++] = j;
cnt++;
}
}
}
sort(save,save+sum);
printf("%d\n",sum);
for(int i = 0; i < sum; i++) {
printf("%d\n",save[i]);
}
if(t) {
printf("\n");
}
}
return 0;
}
本文标签: 区间选点uvaadvertisement
版权声明:本文标题:UVA - 10148 Advertisement(区间选点问题) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1729328141a1196028.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论