题意:给一些工作区间,如何选取最小的工作数量,覆盖[1,T]的工作时长

一开始的思路,当然也是错误的思路:

  • 我想着,最小工作数量是吧?那肯定就是选择结束时间最晚的,给结束时间来一个排序。哎这个思路错误的离谱...

解题思路:

  1. 标记起点,当然对提供的工作区间,按开始的时间从小到大排序。
  2. 对能够覆盖起点(即可选的工作区域),选择结束时间最晚的(即工作时长最长的)
  3. 更新起点

代码中的小技巧

主要针对第二个解题思路:

  1. 可选区域: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 ;
}

最新文章

  1. 学习笔记:7z在delphi的应用
  2. nslookup
  3. 动态加载zTree,用key属性设置url链接、icon图标等
  4. 初学HTML5、初入前端
  5. EXTJS4自学手册——EXT基本方法、属性(mixins多继承、statics、require)
  6. IBM Rational AppScan 无法记录登录序列 分类: 数据安全 2015-03-18 16:46 158人阅读 评论(0) 收藏
  7. Strust2 初体验
  8. 图片延迟加载(lazyload)的实现原理
  9. Hibernate中的一级缓存、二级缓存和懒加载
  10. Coding4Fun.Phone.Controls的使用
  11. osg 基本几何图元
  12. Android Activity间传值
  13. C++中“wchar_t* ”和“ char * ”之间的相互转换
  14. 分布式事务2PC_PENDING异常处理
  15. mybatis_16逆向工程
  16. flask 登录验证码 字母和数字
  17. 第七篇-列表式App:ListActivity及ListView
  18. day05 Python中的set集合
  19. JS的一些小知识
  20. 黄聪:TortoiseGit(乌龟git)保存用户名密码的方法

热门文章

  1. HDU 1024 A - Max Sum Plus Plus DP + 滚动数组
  2. CI框架自带的验证工具及汉化
  3. React Router 4.0中文快速入门
  4. JAVA基础之字节流与字符流
  5. Kendo UI 移动应用开发简介
  6. javascript对象的学习
  7. 本号讯 | 人工智能手表为帕金森患者带来书写希望;微软翻译发布可实时翻译幻灯片的Presentation Translator
  8. JavaScript_4_数据类型
  9. Nginx+Keepalived负载均衡+后端LNMP网站集群
  10. SAP成都研究院DevOps那些事