51Nod 1163 最高的奖励(贪心+优先队列 并差集)

2024-04-20 12:18

本文主要是介绍51Nod 1163 最高的奖励(贪心+优先队列 并差集),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接:最高的奖励

题目大意

有N个任务,每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务,就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的,因为时间上可能会有冲突,这需要你来取舍。求能够获得的最高奖励。
Input
第1行:一个数N,表示任务的数量(2 <= N <= 50000)
第2 - N + 1行,每行2个数,中间用空格分隔,表示任务的最晚结束时间E[i]以及对应的奖励W[i]。(1 <= E[i] <= 10^9,1 <= W[i] <= 10^9)
Output
输出能够获得的最高奖励。

思路1 贪心

用贪心思想,从0开始,每完成一件任务,消耗时间为1,按最晚时间递增,第n个任务如果最晚时间大于已消耗掉时间量,则可算入总和,若不大于已耗时间量,则可以替换掉总和里最小奖励的一个任务(如果当前任务的奖励更多的话)。
这个过程可以用堆维护。nlog(n);

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<functional>
#include<vector>
using namespace std;struct Node
{int l, v;
};
Node node[50009];bool cmp(const Node &a, const Node &b)
{return a.l < b.l;
}int main()
{int n;scanf("%d",&n);priority_queue<int, vector<int>, greater<int> > q;for(int i=0;i<n;i++){scanf("%d%d",&node[i].l, &node[i].v);}sort(node, node+n, cmp);long long ans = 0;for(int i=0;i<n;i++){int num = node[i].v;if(node[i].l > q.size()){ans += num;q.push(num);}else{ans += num;q.push(num);ans -= q.top();q.pop();}}printf("%lld\n",ans);
}

思路2 并差集

因为每个任务完成需要的时间都是1,即每个点都可以完成一次任务,所以可以使用并差集维护当前未使用的时间点,f[x] = a;表示最晚时间为x的任务可以在a点完成
先按奖励降序排列,然后遍历即可,若有可完成任务的时间节点,则完成此任务,奖励算入总和。
O(n*a(n)) a(n)为并差集的查找过程 接近于1

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
#include<functional>
#include<vector>
using namespace std;struct Node
{int l, v;
};
Node node[50009];int f[50009];bool cmp(const Node &a, const Node &b)
{return a.v > b.v;
}int find(int x)
{if(x <= 0)return -1;if(x == f[x])return f[x] = x-1;return f[x] = find(f[x]);
}int main()
{int n;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d%d",&node[i].l, &node[i].v);if(node[i].l > n) node[i].l = n;f[i] = i;}f[n] = n;sort(node, node+n, cmp);long long ans = 0;for(int i=0;i<n;i++){if(find(node[i].l) >= 0)ans += node[i].v;}printf("%lld\n",ans);
}

这篇关于51Nod 1163 最高的奖励(贪心+优先队列 并差集)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/920241

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结

SpringKafka错误处理(重试机制与死信队列)

《SpringKafka错误处理(重试机制与死信队列)》SpringKafka提供了全面的错误处理机制,通过灵活的重试策略和死信队列处理,下面就来介绍一下,具有一定的参考价值,感兴趣的可以了解一下... 目录引言一、Spring Kafka错误处理基础二、配置重试机制三、死信队列实现四、特定异常的处理策略五

Spring Boot整合消息队列RabbitMQ的实现示例

《SpringBoot整合消息队列RabbitMQ的实现示例》本文主要介绍了SpringBoot整合消息队列RabbitMQ的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的... 目录RabbitMQ 简介与安装1. RabbitMQ 简介2. RabbitMQ 安装Spring

如何通过Python实现一个消息队列

《如何通过Python实现一个消息队列》这篇文章主要为大家详细介绍了如何通过Python实现一个简单的消息队列,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录如何通过 python 实现消息队列如何把 http 请求放在队列中执行1. 使用 queue.Queue 和 reque

解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)

《解读Redis秒杀优化方案(阻塞队列+基于Stream流的消息队列)》该文章介绍了使用Redis的阻塞队列和Stream流的消息队列来优化秒杀系统的方案,通过将秒杀流程拆分为两条流水线,使用Redi... 目录Redis秒杀优化方案(阻塞队列+Stream流的消息队列)什么是消息队列?消费者组的工作方式每

Redis延迟队列的实现示例

《Redis延迟队列的实现示例》Redis延迟队列是一种使用Redis实现的消息队列,本文主要介绍了Redis延迟队列的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习... 目录一、什么是 Redis 延迟队列二、实现原理三、Java 代码示例四、注意事项五、使用 Redi

hdu1180(广搜+优先队列)

此题要求最少到达目标点T的最短时间,所以我选择了广度优先搜索,并且要用到优先队列。 另外此题注意点较多,比如说可以在某个点停留,我wa了好多两次,就是因为忽略了这一点,然后参考了大神的思想,然后经过反复修改才AC的 这是我的代码 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s