poj 2376 选择工作区间问题 贪心算法
2024-08-30 03:21:46
题意:给一些工作区间,如何选取最小的工作数量,覆盖[1,T]的工作时长
一开始的思路,当然也是错误的思路:
- 我想着,最小工作数量是吧?那肯定就是选择结束时间最晚的,给结束时间来一个排序。哎这个思路错误的离谱...
解题思路:
- 标记起点,当然对提供的工作区间,按开始的时间从小到大排序。
- 对能够覆盖起点(即可选的工作区域),选择结束时间最晚的(即工作时长最长的)
- 更新起点
代码中的小技巧
主要针对第二个解题思路:
- 可选区域:i<n&&node[i].start<=T+1 --i表示当前循环的工作序号没有超过n,第二个判断语句就是指,当前工作的开始时间小于等于标记的起点+1才可以被选
while(i<n&&node[i].start<=T+1) { end=max(end,node[i].end); i++;}
解题代码:
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <math.h>
using namespace std;
struct Cow
{
int b, e;
}cow[];
int cmp(Cow a, Cow b)
{
return a.b < b.b;
}
int main()
{
int n, t;
int ans = , T = ;
int i = ;
scanf("%d%d", &n, &t);
for (int i = ; i < n; i++)
scanf("%d%d", &cow[i].b, &cow[i].e);
sort(cow, cow + n, cmp);
while (T<t&&i<n)
{
ans++;
int end = T;
if (cow[i].b > T + )
{
break;
}
else
{
while (i<n&&cow[i].b <= T + )
{
end = max(end, cow[i].e);
i++;
}
T = end;
}
if (T >= t)
{
printf("%d\n", ans);
return ;
}
}
if (T >= t)
printf("%d\n", ans);
else
printf("-1\n");
return ;
}
最新文章
- 学习笔记:7z在delphi的应用
- nslookup
- 动态加载zTree,用key属性设置url链接、icon图标等
- 初学HTML5、初入前端
- EXTJS4自学手册——EXT基本方法、属性(mixins多继承、statics、require)
- IBM Rational AppScan 无法记录登录序列 分类: 数据安全 2015-03-18 16:46 158人阅读 评论(0) 收藏
- Strust2 初体验
- 图片延迟加载(lazyload)的实现原理
- Hibernate中的一级缓存、二级缓存和懒加载
- Coding4Fun.Phone.Controls的使用
- osg 基本几何图元
- Android Activity间传值
- C++中“wchar_t* ”和“ char * ”之间的相互转换
- 分布式事务2PC_PENDING异常处理
- mybatis_16逆向工程
- flask 登录验证码 字母和数字
- 第七篇-列表式App:ListActivity及ListView
- day05 Python中的set集合
- JS的一些小知识
- 黄聪:TortoiseGit(乌龟git)保存用户名密码的方法
热门文章
- HDU 1024 A - Max Sum Plus Plus DP + 滚动数组
- CI框架自带的验证工具及汉化
- React Router 4.0中文快速入门
- JAVA基础之字节流与字符流
- Kendo UI 移动应用开发简介
- javascript对象的学习
- 本号讯 | 人工智能手表为帕金森患者带来书写希望;微软翻译发布可实时翻译幻灯片的Presentation Translator
- JavaScript_4_数据类型
- Nginx+Keepalived负载均衡+后端LNMP网站集群
- SAP成都研究院DevOps那些事