按照t2从小到大排列之后贪心。
若当前任务可以插入,则插入。
若当前任务不可以插入,分两种情况:
①当前任务的耗时大于等于之前插入的任务的最大耗时:跳过当前任务
②当前任务的耗时小于之前插入的任务的耗时:将最前插入的耗时最大的那个任务删除,插入当前任务
用堆维护
 
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std; #define MAXN 150010 priority_queue<int>q; int n;
int i;
int res,ans,tmp; struct Node
{
int t,d;
}a[MAXN]; int cmp(Node x,Node y)
{
return x.d<y.d;
} int main()
{
scanf("%d",&n);
for (i=1;i<=n;i++)
scanf("%d%d",&a[i].t,&a[i].d);
sort(a+1,a+n+1,cmp);
for (i=1;i<=n;i++)
if (res+a[i].t<=a[i].d)
{
ans++;
res+=a[i].t;
q.push(a[i].t);
}
else
{
tmp=q.top();
if (a[i].t<tmp)
{
q.pop();
q.push(a[i].t);
res+=a[i].t-tmp;
}
}
printf("%d",ans);
return 0;
}

  

最新文章

  1. httpd安装.md
  2. ftp下载目录下所有文件及文件夹内(递归)
  3. JSP 连接MySQL 5.1
  4. 平行四边形TikZ作图
  5. Maven 的 HelloWorld
  6. C#中的yield return与Unity中的Coroutine(协程)(下)
  7. VBS_For_next
  8. 函数查询(Function Query)
  9. 【网络流24题】 No.14 孤岛营救问题 (分层图最短路)
  10. Android---用动画来处理布局的变化
  11. [转载][NAS] 使用win8的“存储池”功能~
  12. 【百度地图API】关于如何进行城市切换的三种方式
  13. QT 设计师使用样式表添加背景
  14. BZOJ_3944_Sum_杜教筛
  15. springcloud-spring cloud config统一配置中心
  16. Docker for Windows 中文文档(3)——Docker Settings
  17. Web开发——HTML基础(HTML表格 &lt;table&gt;)
  18. Git Pull Github and Gitee or Gitlab
  19. Redis慢查询日志学习功能
  20. openstack 实用命令

热门文章

  1. Java中List集合的遍历
  2. eclipse如何导出WAR包
  3. 牛客网提高组第二场---solution
  4. 网络共享服务器 samba
  5. String与常量池(JDK1.8)
  6. laravel学习笔记3--高级
  7. Buffer.alloc()
  8. 三菱PLC FB库函数调用方法 (Gx Work2版本)
  9. 华中农业大学第四届程序设计大赛网络同步赛-1020: Arithmetic Sequence,题挺好的,考思路;
  10. NIST的安全内容自动化协议(SCAP)以及SCAP中文社区简介