最高的奖励 - 优先队列&贪心 / 并查集
2024-08-28 09:26:00
题目地址: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 ;
}
最新文章
- WebSocket - ( 一.概述 )
- Android studio Gradle 教程
- Java中super的几种用法并与this的区别
- PHP学习笔记:APACHE配置虚拟目录、一个站点使用多域名配置方式
- 如何在DigitalOcean安装Ghost
- 将日志搬家到自己的站点 http://nowhereman.cn/
- TCL语言笔记:TCL中的列表操作
- String str 与 String str=new String(";";) 区别
- the Linux Kernel: Traffic Control, Shaping and QoS
- 加载为应用程序池‘DefaultAppPool&#39;提供服务的进程失败,应用程序池被禁用【解决方法】
- 防止多个UIAlertView重叠弹出
- Spring Boot实战:静态资源处理
- C语言头文件中定义全局变量导致重复定义错误
- Spring MVC深入学习
- [JsonSchema] 关于接口测试 Json 格式比对核心算法实现 (Java 版)
- 【原创】运维基础之OpenResty
- ios UITableView背景图片设置
- SQLSERVER文件组误脱机后如何联机
- 算法学习——从bzoj2286开始的虚树学习生活
- DMA/TIM capture
热门文章
- mystr = &#39;{}{}{}&#39;.format(mystr, random.randint(0, 9), adurl)
- bootrap 手风琴Collapse源码分析
- YTU 2623: B 抽象类-形状
- dom小练习
- securecrt中vim行号下划线问题及SecureCRT里root没有高亮的设置,修改linux终端命令行颜色
- java笔记线程电影院卖票改进版
- E20171214-sl
- [TYVJ1391]走廊泼水节
- 块级标签与预格式化文本标签----------大多数XHTML可以表示为两种类型的标签:块标签(block tag)和内联标签(inline tag)
- 使用jstack精确找到异常代码的