首页 > 代码库 > uva10148Advertisement(区间选点)
uva10148Advertisement(区间选点)
题目: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; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。