51 Nod 1163 最高的奖励
2024-09-04 22:41:55
基准时间限制:1 秒 空间限制:131072 KB 分值: 20 难度:3级算法题
有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
输出能够获得的最高奖励。
Input示例
7
4 20
2 60
4 70
3 40
1 30
4 50
6 10
Output示例
230
思路:将任务按时间先后顺序排序,若时间相同,则奖励高的排在前面。用优先队列维护之前做过的任务的奖励值,考虑当前时刻,如果存在某些当前时间点完不成的任务,如果这些任务的奖励比之间做的奖励(优先队列中)还要大,那么逻辑上将两者交换。
代码:
#include<bits/stdc++.h>
#include<stdio.h>
#include<iostream>
#include<cmath>
#include<math.h>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<algorithm>
#include<stack>
using namespace std;
#define inf 0x3f3f3f3f
typedef long long ll;
struct node
{
int e;
int w;
} a[50005],c[50005];
bool cmp(node n1,node n2)
{
if(n1.e!=n2.e)return n1.e<n2.e;
else {
return n1.w>n2.w;
}
}
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif // ONLINE_JUDGE
ll ans=0;
int n;int cnt=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d%d",&a[i].e,&a[i].w);
if(a[i].e>=n)ans+=a[i].w;
else {
c[cnt++]=a[i];
}
}
sort(c,c+cnt,cmp);
int p=0;int min_pre=0x3f3f3f3f;
for(int i=1;i<=n;i++)
{
while(c[p].e<i&&p<cnt)
{
if(c[p].w>min_pre)
{
ans+=c[p].w-min_pre;
}
q.push(c[p].w);
q.pop();
min_pre=q.top();
p++;
}
if(p==cnt)break;
ans+=c[p].w;
q.push(c[p].w);
min_pre=q.top();
p++;
if(p>=cnt)break;
}
printf("%lld\n",ans);
return 0;
}
最新文章
- HTTP 错误 404.3 – Not Found 由于扩展配置问题而无法提供您请求的页面。如果该页面是脚本,请添加处理程序。如果应下载文件,请添加 MIME 映射。
- Windows 服务快捷启动命令
- C++的隐式类型转换与转换操作符
- 一步一步搭建Jenkins环境
- Intent传递对象的两种方法
- hibernate反向工程 (eclipse和myeclipse)(转)
- 解决 window server2008 r2 没有注册Ofiice组件的方法
- Linux平台Cpu使用率的计算
- Android开发之Bitmap.Config.RGB_565
- C 二叉树
- O(1)时间删除链表节点
- js 实现键盘记录 兼容FireFox和IE
- XamlReader动态使用xaml
- TensorFlow简易学习[3]:实现神经网络
- 比起Windows,怎样解读Linux的文件系统与目录结构?
- day03变量的命名规范,常量,输出:自带换行,输入,注释,数据类型,运算符,常用字符大小关系
- python2.x 到 python3.x 中“url”部分变化
- Spring MVC原理介绍
- C++ 链接Mysql 函数介绍
- UIImageView的一些用法
热门文章
- Vanya and Scales CodeForces - 552C (思维)
- how to Simply Singleton Navigate the deceptively simple Singleton pattern---reference
- C#面向对象10 继承
- 解决vs code编写python输出中文乱码问题
- [CSS] w3c 盒模型 和 IE 盒模型
- 使用docker compose部署服务
- sql DATEDIFF 函数
- Linux下Mysql 不能访问新数据文件夹问题
- 第九章&#183;Logstash深入-Logstash配合rsyslog收集haproxy日志
- 基于Linux解决登录ssh客户端失败问题—sshd error: could not load host key