UVa 10148:Advertisement

【链接】

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1089

【原题】

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 least K times 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 see K billboards. 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 see K billboards, 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 seeing Kadvertisements, 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.

本栏目更多精彩内容:http://www.bianceng.cn/Programming/sjjg/

The first line of each test case contains two integers K and N (1 ≤ K, N ≤ 1000) separated by a space. K is the minimal number of advertisements that every jogger must see, and N is the total number of joggers.

The following N lines describe the path of each jogger. Each line contains two integers Ai and Bi (both numbers are not greater than 10000 by absolute value). Ai represents the first billboard number seen by jogger number i and Bi gives the last billboard number seen by that jogger. During a run, jogger i will see billboards Ai, Bi and all billboards between them.

Output

On the first line of the output fof each test case, write a single integer M. This number gives the minimal number of advertisements that should be placed on billboards in order to fulfill the client's requirements. Then write M lines 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 input

1

5 10
1 10
20 27
0 -3
15 15
8 2
7 30
-1 -10
27 20
2 9
14 21

Sample output for the sample input

19-5-4-3-2-10456781518192021252627

【题目大意】

某条街道上有很多个广告位,一个公司在这条街上投放广告,因为不同地方的人流量是不同的,所以公司先做了个调查,共调查了N个人,知道了他们每个人每天在街上走的路段。现在要求找到一些广告位,使得广告位数量最少,但是要求调查到的那些每人至少看到广告K次。如果有人走的路段广告位少于K个,那么要求他在这个路段的所有广告位都要看到。输出要求的广告位的位置。

【分析与总结】

经典贪心,区间选点问题。《算法入门经典》P154。

假设每个区间是【ai, bi】, 那么先按照每个区间的bi从小到大排序。

下图是排好序的四个区间。为了使得广告位数量最少,那么就要让这些广告位尽量的处在越多人重复经过的地方越好。

观察下图可以看出,为了让重叠部分越多,那么每个区间选点时,就要让这些点尽可能的往改区间的右边靠。

在对每个区间选点时,先查看该区间之前已经被选好几个点了,如果不够的话再补上。

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索path
, 广告
, number
, 区间
, The
that
uva oj、uva和uvb的区别、uvb、uva大学、弗吉尼亚大学,以便于您获取更多的相关知识。

时间: 2016-10-28

UVa 10148:Advertisement的相关文章

UVa 10148 Advertisement:贪心&标记法单个处理

10148 - Advertisement Time limit: 3.000 seconds http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1089 The Department of Recreation has decided that it must be more profitable, and

uva 10148 - Advertisement

点击打开链接uva 101148 题目意思: 公园里有一个广告牌,由于公园里经常有很多人在慢跑锻炼身体,现在有一个客户想在这个广告牌上面贴广告,他想让每一个慢跑的人都能够看到至少k个广告,由于每一个人跑步的路径不同,不同人看到的广告是不同的,可能只看到一个广告.现在规定广告是一序列连续的整数表示,有n个人,每一个能够看到的第一个广告和最后一个广告是已知的,现在要求满足这个客户的要求下(客户要求了要尽量省钱),找到最少需要贴广告的数量,并输出所贴的广告的编号 . 解题思路: 1思路:贪心 2分析:

UVa 1422:Processor 任务处理问题

题目大意:有n个任务送到处理器处理,每个任务信息包括r,d,w,r代表开始时间,w代表必须要结束的时间,w指需要多少时间处理. 其中处理器的处理速度可以变速,问处理器最小需要多大速度才能完成工作? 输入: 3 5 1 4 2 3 6 3 4 5 2 4 7 2 5 8 1 6 1 7 25 4 8 10 7 10 5 8 11 5 10 13 10 11 13 5 8 15 18 10 20 24 16 8 15 33 11 14 14 1 6 16 16 19 12 3 5 12 22 25

UVa 10905:Children's Game

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1846 类型: 排序 There are lots of number games for children. These games are pretty easy to play but not so easy to make. We will

UVa 10763:Foreign Exchange

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1704 原题: Your non-profit organization (iCORE - international Confederation of Revolver Enthusiasts) coordinates a very succes

UVa 10341: Solve It

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1282 原题: Solve the equation:        p*e-x + q*sin(x) + r*cos(x) + s*tan(x) + t*x2 + u = 0        where 0 <= x <= 1. Input

UVa 10057:A mid-summer night&#039;s dream.

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=998 原题: This is year 2200AD. Science has progressed a lot in two hundred years. Two hundred years is mentioned here because thi

UVa 10487:Closest Sums

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1428 原题: Given is a set of integers and then a sequence of queries. A query gives you a number and asks to find a sum of two di

UVa 10340:All in All

链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1281 原题: You have devised a new encryption technique which encodes a message by inserting between its characters randomly gener