[luoguP2949] [USACO09OPEN]工作调度Work Scheduling(贪心 + 优先队列)
2024-08-30 23:01:22
这个题类似于建筑抢修。
先按照时间排序。
如果当前时间小于任务截止时间就选,
否则,看看当前任务价值是否比已选的任务的最小价值大,
如果是,就替换。
可以用优先队列。
——代码
#include <queue>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long const int MAXN = 1e6 + ;
int n;
LL tim, ans;
struct node
{
LL x, y;
}p[MAXN];
std::priority_queue <LL, std::vector <LL>, std::greater <LL> > q; inline LL read()
{
LL x = , f = ;
char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -;
for(; isdigit(ch); ch = getchar()) x = (x << ) + (x << ) + ch - '';
return x * f;
} inline bool cmp(node x, node y)
{
return x.x < y.x;
} int main()
{
int i;
n = read();
for(i = ; i <= n; i++) p[i].x = read(), p[i].y = read();
std::sort(p + , p + n + , cmp);
for(i = ; i <= n; i++)
{
if(tim < p[i].x) tim++, ans += p[i].y, q.push(p[i].y);
else if(tim == p[i].x && p[i].y > q.top())
{
ans += p[i].y - q.top();
q.pop();
q.push(p[i].y);
}
}
printf("%lld\n", ans);
return ;
}
最新文章
- asp.net MVC 回顾 Html.ActionLink
- colorbox 自适应 高度
- xcode更新,想想也是醉了
- GUI创建各常用控件(二)
- Android studio设置参数提示
- Qt如何去掉按钮等控件的虚线框(焦点框)(三种办法)
- (转)Ubuntu中使用dpkg安装deb文件提示依赖关系问题,仍未被配置
- JQuery DOM HighLighter (it's a basic "Inspect element" simple implementation to mimic what webkit inspector and firebug do)
- String类的替换方法(9)
- python3学习笔记(3)
- SSM实战
- Python中and(逻辑与)计算法则
- [Swift]LeetCode95. 不同的二叉搜索树 II | Unique Binary Search Trees II
- GIS开发 图形常见算法
- vs2015 不能启动 iis express
- ArrayList实现动态数组原理
- dns 安全可视化
- 企业数据总线(ESB)和注册服务管理(dubbo)的区别
- vue中封装公共方法,全局使用
- c# 连等的写法都做了什么?
热门文章
- bzoj 1715: [Usaco2006 Dec]Wormholes 虫洞【spfa判负环】
- vim 跳行查看日志
- hdu5926Mr. Frog’s Game
- Spring抽象JDBC,使用JdbcTemplate
- 235 Lowest Common Ancestor of a Binary Search Tree 二叉搜索树的最近公共祖先
- [ USACO 2001 OPEN ] 地震
- Python自动监控错误日志
- R语言学习 - 热图美化
- 扩增子分析解读4去嵌合体 非细菌序列 生成代表性序列和OTU表
- The following packages have unmet dependencies: