首页 > 代码库 > UVA10148- Advertisement(区间选点)
UVA10148- Advertisement(区间选点)
题意:一段路上,给出n个慢跑者跑步的区间,给出k,要求让每个慢跑者都能看到k个广告,区间都是整数操作,也就是说一个广告只能放在一个整数上,求最小贴的广告数
思路:关于区间选点的问题。把所有区间按B从小到大排序(B相同时A从大到小排序),则如果出现区间包含的情况,小区间一定排在前面。所以贪心的策略就是,从后往前取k个点。因为只有从后面开始取点,满足的区间才最会最多,这样就能达到使用最少的点的目的。注意如果区间长度小于k的话,区间内所有点都要取到。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 10000; struct jogger{ int A, B; }p[MAXN]; int vis[MAXN * 2 + 5]; int k, n, cnt; int cmp(jogger a, jogger b) { if (a.B != b.B) return a.B < b.B; return a.A > b.A; } int main() { int cas; scanf("%d", &cas); while (cas--) { scanf("%d %d", &k, &n); for (int i = 0; i < n; i++) { scanf("%d %d", &p[i].A, &p[i].B); p[i].A += MAXN; p[i].B += MAXN; if (p[i].A > p[i].B) swap(p[i].A, p[i].B); } cnt = 0; memset(vis, 0, sizeof(vis)); sort(p, p + n, cmp); for (int i = 0; i < n; i++) { if (p[i].B - p[i].A <= k - 1) { for (int j = p[i].A; j <= p[i].B; j++) if (!vis[j]) { vis[j] = 1; cnt++; } } else { int temp = 0; for (int j = p[i].A; j <= p[i].B; j++) if (vis[j]) temp++; if (temp >= k) continue; for (int j = p[i].B; j >= p[i].A; j--) { if (!vis[j]) { vis[j] = 1; cnt++; temp++; } if (temp >= k) break; } } } printf("%d\n", cnt); for (int i = 0; i < MAXN * 2 + 5; i++) if (vis[i] && cnt) { printf("%d\n", i - MAXN); cnt--; } if (cas) printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。