uva 10148 Advertisement
The Department of Recreation has decided that it must be more profitable, and it wants to sell advertising space along a popular jogging path at a local park. They have built a number of billboards (special signs for advertisements) along the path and have decided to sell advertising space on these billboards. Billboards are situated evenly along the jogging path, and they are given consecutive integer numbers corresponding to their order along the path. At most one advertisement can be placed on each billboard.
A particular client wishes to purchase advertising space on these billboards but needs guarantees that every jogger will see it’s advertisement at leastKtimes while running along the path. However, different joggers run along different parts of the path.
Interviews with joggers revealed that each of them has chosen a section of the path which he/she likes to run along every day. Since advertisers care only about billboards seen by joggers, each jogger’s personal path can be identified by the sequence of billboards viewed during a run. Taking into account that billboards are numbered consecutively, it is sufficient to record the first and the last billboard numbers seen by each jogger.
Unfortunately, interviews with joggers also showed that some joggers don’t run far enough to seeKbillboards. Some of them are in such bad shape that they get to see only one billboard (here, the first and last billboard numbers for their path will be identical). Since out-of-shape joggers won’t get to seeKbillboards, the client requires that they see an advertisement on every billboard along their section of the path. Although this is not as good as them seeingKadvertisements, this is the best that can be done and it’s enough to satisfy the client.
In order to reduce advertising costs, the client hires you to figure out how to minimize the number of billboards they need to pay for and, at the same time, satisfy stated requirements.
Input
The first line of the input consist of an integer indicating the number of test cases in theinput. Then there’s a blank line and the test cases separated by a blank line.
The first line of each test case contains two integersKandN(1≤K,N≤1000) separated by a space.Kis the minimal number of advertisements that every jogger must see, andNis the total number of joggers.
The followingNlines describe the path of each jogger. Each line contains two integersAiandBi(both numbers are not greater than 10000 by absolute value).Airepresents the first billboard number seen by jogger numberiandBigives the last billboard number seen by that jogger. During a run, joggeriwill see billboardsAi,Biand all billboards between them.
Output
On the first line of the output fof each test case, write a single integerM. This number gives the minimal number of advertisements that should be placed on billboards in order to fulfill the client’s requirements. Then writeMlines with one number on each line. These numbers give (in ascending order) the billboard numbers on which the client’s advertisements should be placed. Print a blank line between test cases.
Sample input15 101 1020 270 -315 158 27 30-1 -1027 202 914 21Sample output for the sample input19-5-4-3-2-10456781518192021252627
题目大意：每组数据包括两个部分：
1）K 和 N ，K是每位慢跑者至少要看到的广告数，N 是慢跑者的数量。
2）接下来 N 行是 N 个慢跑者的行进区间（区间无序，需要先判断左右边界）。
求满足要求所需贴的最少广告数，，并按顺序输出广告的位置。
解题思路：区间选点问题。先将N个区间，按右区间大小从小到大排序（若右区间相同，则按左区间从大到小排序）。然后从每个区间右边开始贴广告，直到贴满K张广告，或贴满当前慢跑者的行进区间。
#include<stdio.h>#include<string.h>#include<stdlib.h>#include<algorithm>using namespace std;struct JOG{int b, f;};JOG jog[1005];int k, n, rec[1005], vis[20010];int cmp(JOG a, JOG b) {if (a.f != b.f) {return a.f < b.f;}else return a.b > b.b;}int main() {int T;scanf("%d", &T);while (T–) {scanf("%d %d", &k, &n);int Max = -1000, Min = 1000;for (int i = 0; i < n; i++) {int a, b;scanf("%d %d", &a, &b);if (b > a) {jog[i].b = a, jog[i].f = b;}else {jog[i].b = b, jog[i].f = a;}Max = max(Max, jog[i].f);Min = min(Min, jog[i].b);}sort(jog, jog + n, cmp);memset(vis, 0, sizeof(vis));int cnt = 0, temp;for (int i = 0; i < n; i++) {temp = 0;for (int j = jog[i].b; j <= jog[i].f; j++) {if (vis[j + 10000]) temp++;}temp = k – temp;for (int j = jog[i].f; j >= jog[i].b && temp > 0; j–) {if (!vis[j + 10000]) { //j会为负vis[j + 10000] = 1;temp–;cnt++;}}}printf("%d\n", cnt);for (int i = Min; i <= Max; i++) {if (vis[i + 10000]) printf("%d\n", i);}if (T) printf("\n");}return 0;}
听过许多故事，见过旅行风景，就这样，
