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