【题目大意】
给出几个小区间和大区间,求覆盖整个大区间的最少小区间个数,如果不可能则输出-1。
【思路】
这道程序写得我很不爽快,迷迷糊糊写完了,提交一遍AC了,可是我自己都没怎么弄懂到底是怎么写出来的(我果然不是很擅长贪心的实现)。思路很简单,显而易见地贪心,关键在于如何实现这个思路。
先以区间左边界为关键字进行排序,每次选左边界能与上一个右边界相接的区间中右边界最大的那一个。我的实现方法是这样的:假设当前已经覆盖区域的右边界为lright,之前能覆盖到的最大右边界为p,ans为需要的小区间数。对于每一个小区间:
(1)如果它的左边界已经大于lright+1,即p已经是能与上一个右边界相接的区间中右边界最大的那一个,将lright更新为p,p初始化为-1,ans+1;当然,如果p本身就是-1,说明无法与已覆盖区域连接,无解(当然无解的情况并不仅限于这一种,还有可能是无法覆盖到大区间的右边界等),可以直接退出循环。
(2)如果当前左边界小于等于lright+1,且右边界大于等于lright+1,在当前右边界和p中选取较大的一个;如果p恰好大于等于大区间的右边界,ans+1,退出循环。
要注意的一点事,所谓衔接不是[0,1][1,2]这样首尾相接,而是[0,1][2,3]即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int MAXN=+;
struct interval
{
int left,right;
bool operator < (const interval &x) const
{
return (left<x.left);
}
}; int n,t;
interval cow[MAXN]; int main()
{
scanf("%d%d",&n,&t);
for (int i=;i<n;i++)
scanf("%d%d",&cow[i].left,&cow[i].right);
sort(cow,cow+n); int lright=,ans=,p=-;
for (int i=;i<n;i++)
{
if (cow[i].left>lright+)
{
if (p==-) break;
/*如果当前左边界已经大于之前的最大右边界,且没有中间区间能衔接,必定说明无解*/
ans++;
lright=p;
p=-;
/*否则将已经覆盖区域的右边界设为之前最大的右边界*/
}
if (cow[i].left<=lright+ && cow[i].right>=lright+)
{
p=max(p,cow[i].right);
if (p>=t)
{
ans++;
break;
/*如果当前已经覆盖完大区间,就退出*/
}
}
}
if (p>=t) cout<<ans<<endl;
else cout<<-<<endl;
return ;
}
【贪心】POJ2376-Cleaning Shifts的更多相关文章
-
POJ2376 Cleaning Shifts
题意 POJ2376 Cleaning Shifts 0x50「动态规划」例题 http://bailian.openjudge.cn/practice/2376 总时间限制: 1000ms 内存限制 ...
-
POJ2376 Cleaning Shifts 【贪心】
Cleaning Shifts Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 11542 Accepted: 3004 ...
-
poj2376 Cleaning Shifts【线段树】【DP】
Cleaning Shifts Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 32561 Accepted: 7972 ...
-
poj-2376 Cleaning Shifts (排序+贪心)
http://poj.org/problem?id=2376 john有n头牛做打扫工作,他想在t时间内每个时间都至少有一头牛在做打扫工作,第一头牛在1,最后一头牛在t时间,每一头牛工作都有一个开始时 ...
-
poj2376 Cleaning Shifts(区间贪心,理解题意)
https://vjudge.net/problem/POJ-2376 题意理解错了!!真是要仔细看题啊!! 看了poj的discuss才发现,如果前一头牛截止到3,那么下一头牛可以从4开始!!! # ...
-
poj2376 Cleaning Shifts 区间贪心
题目大意: (不说牛了) 给出n个区间,选出个数最少的区间来覆盖区间[1,t].n,t都是给出的. 题目中默认情况是[1,x],[x+1,t]也是可以的.也就是两个相邻的区间之间可以是小区间的右端与大 ...
-
【POJ - 2376】Cleaning Shifts(贪心)
Cleaning Shifts Descriptions: 原文是English,我这就直接上Chinese了,想看原文的点一下链接哦 大表哥分配 N (1 <= N <= 25,000) ...
-
POJ 2376 Cleaning Shifts 贪心
Cleaning Shifts 题目连接: http://poj.org/problem?id=2376 Description Farmer John is assigning some of hi ...
-
Cleaning Shifts(POJ 2376 贪心)
Cleaning Shifts Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 15143 Accepted: 3875 ...
-
bzoj 3389: [Usaco2004 Dec]Cleaning Shifts安排值班 -- 贪心
3389: [Usaco2004 Dec]Cleaning Shifts安排值班 Time Limit: 1 Sec Memory Limit: 128 MB Description 一天有 ...
随机推荐
-
jsp xml servlet
什么都懂一点,什么都不精通!!
-
js添加确认删除操作注意事项
function delsure(){ if(confirm('确认删除吗?')){ return true;//点击确定则返回这里的内容 }else{ return false; } } 在表单中添 ...
-
大熊君说说JS与设计模式之------命令模式Command
一,总体概要 1,笔者浅谈 日常生活中,我们在看电视的时候,通过遥控器选择我们喜欢的频道时,此时我们就是客户端的角色,遥控器的按钮相当于客户请求,而具体执行的对象就是命令对象, 命令模式把一个请求或者 ...
-
valueOf跟toString区别
1.用法如下:toString()方法:返回对象的字符串表示. 对象 操作 Array 将 Array 的元素转换为字符串.结果字符串由逗号分隔,且连接起来. Boolean 如果 Boolean 值 ...
-
C#中唯一标识符GUID的一些知识点
概念 GUID: 即Globally Unique Identifier(全球唯一标识符) 也称作 UUID(Universally Unique IDentifier) . GUID是一个通过特定算 ...
-
link 与 @import之对比
页面中使用CSS的方式主要有3种:行内添加定义style属性值,页面头部内嵌调用和外面链接调用,其中外面引用有两种:link和@import.外部引用CSS两种方式link和@import的方式分别是 ...
-
ios中获取当前屏幕尺寸的方法
//获取当前屏幕尺寸 CGRect screenFrame = [UIScreen mainScreen].bounds; int screenWidth = screenFrame.size.wid ...
-
Oracle的一些命令
sqlldr: 一般用于导入以任何后缀结束的文件,我这次就是因为要导入一张以.20160101为后缀的文件,当初简直束手无策 结合input.ctl使用,可以在DOS下使用,可以对一张表导入数十万,百 ...
-
堆以及一些用法 QWQ这是写得最认真的板子题
最近一直在学图论,然后吧,由于学的东西实在是太多太杂了,加上蒟蒻本蒻又经常颓,所以落了好多好多板子题的整理没写啊嘤嘤嘤,不过把这些东西学的差不多了,再一块写个整理,其实感觉还不错?????也算是很神奇 ...
-
oracle 报错无法从套接字获取更多数据
报错信息如下: ---查看_optimizer_join_elimination_enabled参数值 切换sys用户 select a.ksppinm name, b.ksppstvl value, ...