博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
poj2376 Cleaning Shifts 区间贪心
阅读量:4603 次
发布时间:2019-06-09

本文共 1424 字,大约阅读时间需要 4 分钟。

题目大意:

  (不说牛了)

  给出n个区间,选出个数最少的区间来覆盖区间[1,t]。n,t都是给出的。

  题目中默认情况是[1,x],[x+1,t]也是可以的。也就是两个相邻的区间之间可以是小区间的右端与大区间的左端相差1。这个是看题解才知道的。

 

解题思路:

  贪心题的关键是找到贪心策略。但是这题的贪心策略没那么明显。并且贪心策略没有特定地去选择某一区间。这一题最重要的是要知道在什么情况下才需要增加一个区间。

  首先是进行排序,按照区间的左端从小到大排序,左端相同的按照右端从小到大排。

  从头开始遍历(只能是一重循环,不然要超时了)。当遍历到于第i个区间[xi,yi]时,做下面的事情:

  1、设e为当前所有已经选择的区间的最右端。如果xi<=e+1,那么就代表这个区间很可能被选择。当然这样的区间可能有很多,所以我们需要去找最优的区间。

  2、在满足1的条件下,也就是xi<=e+1。设b为遍历过的所有区间的右端的最大值。如果i区间的右端点yi>b,就把b更新为yi。用一个flag来标记b是否更新过。所以这时候可以用flag=1来标记b更新过了。b有没有更新过有什么区别呢?b没有更新,代表这i区间一定不会被选择。

  3、在flag的值没有改变的前提下,查看一下第i+1和区间的左端点xi+1是否大于e+1。是大于的话,代表着被选择的区间数需要增加一个。因为不选择i区间就会产生断层。然后再把e更新为b,flag标记为0。这样做的话,需要自己增加一个区间,使得左端点大于题目中设定的T。

  “被选择的区间需要增加一个”,不代表i区间一定被选择,也可能是它前面的区间被选择。

例如:

这一组数据

8 14

1 2
1 3
2 3
2 10
3 9
5 7
8 11
11 14

遍历到3 9这一区间,e=3,b=10,cnt=1。cnt是选择的区间数。发现下一组数据的左端点5,已经大于e+1。所以x需要+1。但是我们会发现被选择的区间不是[3,9],应该是[2,10]。

 

代码:

1 #include
2 #include
3 #include
4 #include
5 using namespace std; 6 7 const int N=25010; 8 pair
s[N]; 9 int main()10 {11 //freopen("test.txt","r",stdin);12 int n,i,t;13 while(scanf("%d%d",&n,&t)!=EOF){14 for(i=0;i
e+1&&flag)26 {27 e=b;28 x++;29 flag=0;30 }31 }32 //printf("%d %d %d %d %d %d\n",s[i].first,s[i].second,e,b,flag,x);33 }34 if(e
View Code

 

 

转载于:https://www.cnblogs.com/Potato-lover/p/4194497.html

你可能感兴趣的文章
先行者长虹佳华超融合市场沙龙在京举行
查看>>
建立备份策略的重要性
查看>>
小白用户如何轻松上云 -我的轻量应用服务器探索记
查看>>
BCG与阿里研究院等联合揭秘中国互联网经济:成功的关键是什么?
查看>>
发力IoT领域 Marvell注重生态系统发展
查看>>
数据中心网络布线工程必备七大件
查看>>
20个问题揭穿冒牌数据科学家
查看>>
你应该知道的 RPC 原理
查看>>
Ubuntu安装词典
查看>>
KVM虚拟机在线添加网卡
查看>>
Spring解析
查看>>
支付宝签约教程及注意事项
查看>>
设计模式——组合模式(Composite Pattern)
查看>>
java设计模式之——代理模式
查看>>
Perl DBI模块的例子
查看>>
python中str和repr区别
查看>>
升级win10后无法使用桥接网络解决方法
查看>>
如何进行跨网段的远程唤醒
查看>>
数据挖掘-同比与环比
查看>>
nginx+php详解
查看>>