bzoj1572 [Usaco2009 Open]工作安排Job【贪心 堆】
2024-09-03 07:49:43
传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1572
尽管这一题没有看题解,但是耗时还是比本应耗费的时间要长,所以还是写一下,以提升经验
这一题一看就是贪心,贪心最常用的数据结构就是堆,单调栈,单调队列。尽管想到了这,但是之后脑子就卡壳了,怎么都想不出来。。。
这一题的真谛就是“能选就选,不能选就尝试换”,怎么理解呢?首先先按结束时间排序。每选一个,就把它扔进小根堆里。如果时间允许,当然就选啦。如果时间不允许,就对比堆顶的利润是否比当前这个小,若小,果断弹出,选当前这个。这样子,总时间没变,但是利润增加了。
#include <cstdio>
#include <algorithm>
#include <queue> const int maxn = ; int n, now;
long long ans;
struct st1 {
long long d, p;
} a[maxn];
struct st2 {
long long data;
bool operator<(const st2 rhs) const {
return data > rhs.data;
}
};
std::priority_queue<st2> hp; bool cmp(const st1 & aa, const st1 & ss) {
return aa.d < ss.d;
} int main(void) {
//freopen("in.txt", "r", stdin);
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
scanf("%lld%lld", &a[i].d, &a[i].p);
}
std::sort(a + , a + n + , cmp); for (int i = ; i <= n; ++i) {
if (now < a[i].d) {
ans += a[i].p;
++now;
hp.push((st2){a[i].p});
}
else if (a[i].p > hp.top().data) {
ans += a[i].p - hp.top().data;
hp.pop();
hp.push((st2){a[i].p});
}
}
printf("%lld\n", ans);
return ;
}
希望下一次做这种(水)题能快一点想到。。。
最新文章
- C#接口和抽象类的区别
- mysql 日期格式化
- SublimeText2 快捷键一览
- Windows上常见的集中布尔类型的比较
- [BZOJ 3894] 文理分科 【最小割】
- [Javascript] Call Stack
- Windows 下如何安装配置Snort视频教程
- 10亿美元融资腾讯跟头,Grail要用基因测序做癌症早期筛查
- Angular企业级开发(10)-Smart Table插件开发
- flume1.8 Channel类型介绍(四)
- Java多线程的创建与简单使用
- python数据结构之选择排序
- 【AI】PaddlePaddle-Docker运行
- java 线程Thread 技术--volatile关键字
- myeclispe 一直运行debug问题
- 2017-2018-2 20155303『网络对抗技术』Exp7:网络欺诈防范
- underscore.js源码研究(3)
- 洛谷P4720 【模板】扩展卢卡斯
- 下载tensorflow-gpu版本的源
- STM32定时器级联 -- AN2592
热门文章
- C++设计模式之适配器模式(二)
- Hibernate中的自己定义类型——UserType、CompositeUserType
- CxImage的编译及简单使用举例
- 国内博客(blog)搬家工具(服务)大全
- 【CODEFORCES】 C. Dreamoon and Strings
- jsp_类的封装_集合的应用
- c/c++内存使用原则
- ubuntu php5.6源码安装
- HttpWebRequest以及HttpWebResponse
- codeforces 689C C. Mike and Chocolate Thieves(二分)