最高的奖励

时间限制:1000 ms  |  内存限制:65535 KB
难度:3
 
描述

请问:挖掘机技术哪家强?AC了告诉你!

给你N(N<=3*10^4)个任务,每个任务有一个截止完成时间t(1=<t<=10^9)和完成该任务的奖励v(1=<v<=10^9),每个任务要花一天完成,问最多能获得多少奖励?

 
输入
多组 测试数据。
第一行一个数N,表示任务总数。
接下来N行,每行两个数t和v,如上所述。
输出
对于每组数据输出最高的奖励。
样例输入
7
4 20
2 60
4 70
3 40
1 30
4 50
6 10
样例输出
230
来源
51nod
上传者
TC_赵坤垚

解题:优先队列。。

 #include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <climits>
#include <vector>
#include <queue>
#include <cstdlib>
#include <string>
#include <set>
#include <stack>
#define LL long long
#define INF 0x3f3f3f3f
#define pii pair<int,int>
using namespace std;
const int maxn = ;
pii d[maxn];
int main(){
int n,u,v;
priority_queue< pii,vector< pii >,greater< pii > > q;
while(~scanf("%d",&n)){
LL ans = ;
while(!q.empty()) q.pop();
for(int i = ; i < n; ++i)
scanf("%d %d",&d[i].first,&d[i].second);
sort(d,d+n);
for(int i = ; i < n; ++i){
if(q.size() < d[i].first){
ans += d[i].second;
q.push(make_pair(d[i].second,d[i].first));
}else if(q.size() == d[i].first){
if(d[i].second > q.top().first){
ans += d[i].second - q.top().first;
q.pop();
q.push(make_pair(d[i].second,d[i].first));
}
}
}
printf("%lld\n",ans);
}
return ;
}

最新文章

  1. git 提交代码到github错误处理
  2. JS 跳转页面 在新的选项卡打开
  3. Android Fragment应用实战,使用碎片向ActivityGroup说再见
  4. 在Java中调用C
  5. linux用户管理命令
  6. eclipse使用jetty插件出现内存溢出解决方案
  7. redis 性能监控和排查
  8. vmware虚拟机迁移系统到其它磁盘(xjl456852原创)
  9. 禅道---Bug管理模块
  10. json标准是双引号
  11. UE4读取本地XML文件
  12. 【流媒体开发】VLC Media Player - Android 平台源码编译 与 二次开发详解 (提供详细800M下载好的编译源码及eclipse可调试播放器源码下载)
  13. 工作笔记6-java相关
  14. 网页Title加LOGO图标
  15. poj 2528 Mayor’s posters 【离散化】+【线段树】
  16. Fiddler使用
  17. 16. 3Sum Closest(双指针)
  18. Webservice之axis
  19. C++的技术探究
  20. keepalived启动不成功,状态一直是inactive(dead) 的解决办法以及keepalived高版本没有rc.d目录,虚拟VIP无法访问问题

热门文章

  1. CF43A Football
  2. Windows-命令窗口-强制关机命令
  3. POJ 2189
  4. 为屏而生,为屏而死 - IT &amp;quot;精英”们的杯与具
  5. 【云快讯】之四十八《IBM和Cisco最新收购,加强Openstack易用能力》
  6. Android通过Intent.ACTION_CLOSE_SYSTEM_DIALOGS监听Home按键消息
  7. Ubuntu14.04编译WebRTC For Android代码 2014-07-24
  8. 通过setSystemUiVisibility实现状态栏跟Activity之间的位置关系
  9. C# WebQQ协议群发机器人(二)
  10. hdoj--1251--统计难题(字典树)