【链接】
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.
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
-1
0
4
5
6
7
8
15
18
19
20
21
25
26
27
【题目大意】
某条街道上有很多个广告位,一个公司在这条街上投放广告,因为不同地方的人流量是不同的,所以公司先做了个调查,共调查了N个人,知道了他们每个人每天在街上走的路段。现在要求找到一些广告位,使得广告位数量最少,但是要求调查到的那些每人至少看到广告K次。如果有人走的路段广告位少于K个,那么要求他在这个路段的所有广告位都要看到。输出要求的广告位的位置。
【分析与总结】
经典贪心,区间选点问题。《算法入门经典》P154。
假设每个区间是【ai, bi】, 那么先按照每个区间的bi从小到大排序。
下图是排好序的四个区间。为了使得广告位数量最少,那么就要让这些广告位尽量的处在越多人重复经过的地方越好。
观察下图可以看出,为了让重叠部分越多,那么每个区间选点时,就要让这些点尽可能的往改区间的右边靠。
在对每个区间选点时,先查看该区间之前已经被选好几个点了,如果不够的话再补上。
【代码】
/*
* UVa: 10148 - Advertisement
* Time: 0.080s
* Author: D_Double
*
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 20005
#define ADD 10000
using namespace std;
int K,N;
bool vis[MAXN];
struct Node{
int left;
int right;
friend bool operator < (const Node &a,const Node &b){
return a.right<b.right;
}
}arr[1005];
void solve(){
sort(arr,arr+N);
memset(vis, 0, sizeof(vis));
int sum=0;
for(int i=0; i<N; ++i){
if(arr[i].right-arr[i].left+1<=K){
for(int j=arr[i].left; j<=arr[i].right; ++j)if(!vis[j]){
++sum;
vis[j]=true;
}
}
else{
int cnt=0;
for(int j=arr[i].left; j<=arr[i].right; ++j)if(vis[j]){
++cnt;
}
if(cnt>=K) continue;
for(int j=arr[i].right; j>=arr[i].left; --j)if(!vis[j]){
vis[j]=true;
++cnt;
++sum;
if(cnt>=K)
break;
}
}
}
printf("%d\n",sum);
for(int i=0; i<20005; ++i)if(vis[i]){
printf("%d\n",i-ADD);
}
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&K,&N);
for(int i=0; i<N; ++i){
scanf("%d%d",&arr[i].left,&arr[i].right);
arr[i].left+=ADD, arr[i].right+=ADD;
if(arr[i].right<arr[i].left){
int t=arr[i].left;
arr[i].left=arr[i].right;
arr[i].right=t;
}
}
solve();
if(T) printf("\n");
}
return 0;
}
分享到:
相关推荐
jar包,亲测可用
jar包,亲测可用
jar包,亲测可用
opencv-CFR-advertisement-system-Win
暗示性广告出价移动平台作为大数据分析最终项目的一部分演示视频:
JMeterPlugins-Standard-1.4.0.zip ServerAgent-2.2.1.zip
NULL 博文链接:https://chongz.iteye.com/blog/1543075
2017年上半年(5月份)软考 系统分析师上午真题及答案解析,全网最清晰,答案最正确的真题资料。小任老师出品,必属精品。
文件说明: 这是一个dos7.1的ghost磁盘镜像文件 里面包括全套DOS,UCDOS70,使用时需要安装, cd\ucdos70 install 还包括dos版的diskgen 使用方法 ...点OK,点YES....重启电脑选择U盘启动就可以启动了.
暗示性广告出价移动平台 大数据分析 这是大数据分析课程最终项目源代码。 子目录中的 Java 文件是 Android 源代码,其中 Mahout_Source_File.java 文件包含 Mahout 推荐引擎源代码。
微信小程序开发-超级跑腿一体包案例源码.zip
Axure原型模版,包含多套网页(常用网页,电商高保真网页)axure原型模版,ICON图标等,可直拦复制使用。
缠论 线段精确划分 缠中说禅,中枢,结构
2008年网易应聘资料(很全,包括笔试,面试题和部分答案),相当不错,冯慧军强烈推荐!!!!
大数据学习文档,其中包含有,MR,hive,sqoop,zk,flume,等等,恰同学少年,风华正茂,挥斥方遒。
JUnit API JUnit API JUnit API JUnit API JUnit API
储能电站总体技术方案.pdf
unity多人射击游戏源码Shooter IO - Multiplayer Shooting Arena 1.06 所支持的Unity版本:2017.2.0 及以上版本 ...- Advertisement Monetization - Collectibles powerups - Mobile and Keyboard input
转自 云风'blog 2013-1-31 22:49:58 "我上次通读 Lua 的源代码时,Lua 还在 5.1 。当然 Lua 5.0 我也读过,4.0 和 3.2 则读的不多。 最近有一点空闲,想续写我那本 Lua 源码欣赏。按我心里的计划,还有大约 6 章。...
(1)面向对象分析中,对象是类的实例。对象的构成成分包含了(1),属性和方法(或操作)。 A.... B.... C....D....(2)UML2.0所包含的图中,(2) 描述由模型本身分解而成的组织单元,以及他们之间的依赖关系。...