题目地址:http://www.51cpc.com/web/problem.php?id=1587

Summarize:

优先队列&贪心: 1. 按价值最高排序,价值相同则按完成时间越晚为先;

        2. 使用数组记录时间节点是否有任务,时间节点从最晚倒序遍历;

        3. 若此刻时间节点有任务,则从此时间节点往前推,直到某一刻无任务,否则放弃该任务;

附贪心代码:

(此处并未使用优先队列,以vector代替)

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
#define LL long long const int N = 5e5+;
int n;
struct Task {
LL t,v;
bool operator<(const Task &a) {
return v == a.v? t>a.t: v>a.v;
}
};
vector<Task> task;
int vis[N]; int main()
{
ios::sync_with_stdio(false); while(cin>>n)
{
LL ans=, count=;
for(int i=; i<n; i++) {
vis[i]=;
LL t,v;
cin>>t>>v;
task.push_back(Task{t,v});
} sort(task.begin(), task.end());
for(int i=; i<n; i++) {
int t = task[i].t;
while(vis[t] && t) t--;
if(!t) continue; vis[t] = ;
ans += task[i].v;
if(++count == n)
break;
} cout<<ans<<endl;
task.clear();
} return ;
}

最新文章

  1. WebSocket - ( 一.概述 )
  2. Android studio Gradle 教程
  3. Java中super的几种用法并与this的区别
  4. PHP学习笔记:APACHE配置虚拟目录、一个站点使用多域名配置方式
  5. 如何在DigitalOcean安装Ghost
  6. 将日志搬家到自己的站点 http://nowhereman.cn/
  7. TCL语言笔记:TCL中的列表操作
  8. String str 与 String str=new String(&quot;&quot;) 区别
  9. the Linux Kernel: Traffic Control, Shaping and QoS
  10. 加载为应用程序池‘DefaultAppPool&#39;提供服务的进程失败,应用程序池被禁用【解决方法】
  11. 防止多个UIAlertView重叠弹出
  12. Spring Boot实战:静态资源处理
  13. C语言头文件中定义全局变量导致重复定义错误
  14. Spring MVC深入学习
  15. [JsonSchema] 关于接口测试 Json 格式比对核心算法实现 (Java 版)
  16. 【原创】运维基础之OpenResty
  17. ios UITableView背景图片设置
  18. SQLSERVER文件组误脱机后如何联机
  19. 算法学习——从bzoj2286开始的虚树学习生活
  20. DMA/TIM capture

热门文章

  1. mystr = &#39;{}{}{}&#39;.format(mystr, random.randint(0, 9), adurl)
  2. bootrap 手风琴Collapse源码分析
  3. YTU 2623: B 抽象类-形状
  4. dom小练习
  5. securecrt中vim行号下划线问题及SecureCRT里root没有高亮的设置,修改linux终端命令行颜色
  6. java笔记线程电影院卖票改进版
  7. E20171214-sl
  8. [TYVJ1391]走廊泼水节
  9. 块级标签与预格式化文本标签----------大多数XHTML可以表示为两种类型的标签:块标签(block tag)和内联标签(inline tag)
  10. 使用jstack精确找到异常代码的