传送门: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 ;
}

希望下一次做这种(水)题能快一点想到。。。

最新文章

  1. C#接口和抽象类的区别
  2. mysql 日期格式化
  3. SublimeText2 快捷键一览
  4. Windows上常见的集中布尔类型的比较
  5. [BZOJ 3894] 文理分科 【最小割】
  6. [Javascript] Call Stack
  7. Windows 下如何安装配置Snort视频教程
  8. 10亿美元融资腾讯跟头,Grail要用基因测序做癌症早期筛查
  9. Angular企业级开发(10)-Smart Table插件开发
  10. flume1.8 Channel类型介绍(四)
  11. Java多线程的创建与简单使用
  12. python数据结构之选择排序
  13. 【AI】PaddlePaddle-Docker运行
  14. java 线程Thread 技术--volatile关键字
  15. myeclispe 一直运行debug问题
  16. 2017-2018-2 20155303『网络对抗技术』Exp7:网络欺诈防范
  17. underscore.js源码研究(3)
  18. 洛谷P4720 【模板】扩展卢卡斯
  19. 下载tensorflow-gpu版本的源
  20. STM32定时器级联 -- AN2592

热门文章

  1. C++设计模式之适配器模式(二)
  2. Hibernate中的自己定义类型——UserType、CompositeUserType
  3. CxImage的编译及简单使用举例
  4. 国内博客(blog)搬家工具(服务)大全
  5. 【CODEFORCES】 C. Dreamoon and Strings
  6. jsp_类的封装_集合的应用
  7. c/c++内存使用原则
  8. ubuntu php5.6源码安装
  9. HttpWebRequest以及HttpWebResponse
  10. codeforces 689C C. Mike and Chocolate Thieves(二分)