51nod1163【贪心】
2024-08-24 21:18:11
思路:
我们可以说:
①:价值大的不管时间早晚,都可以取,时间较晚的,本身就可以取,那么肯定是大的在前面取,但是在最前面那也是不对的,那么条件就是在规定的时间内,大的就是取了,因为他大,OK。
②:只要时间允许,怎么取都无所谓,时间不允许取所有,挑大的,如果时间上满足就加了,不满足的话我们要挑个比他小的而且时间还要在他前面。
所以贪心策略就是先按照时间排下序,然后按照上面的想法操作。
#include <stdio.h>
#include <queue>
#include <map>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=5e4+10;
struct asd{
int t;
LL val;
};
asd q[N];
bool cmp(asd x,asd y)
{
return x.t<y.t;
}
int main()
{
int n;
scanf("%d",&n);
for(int i=0;i<n;i++)
scanf("%d%lld",&q[i].t,&q[i].val);
sort(q,q+n,cmp);
LL ans=0;
priority_queue<int ,vector<int >,greater<int> >que;
for(int i=0;i<n;i++)
{
if(q[i].t>que.size())
{
ans+=q[i].val;
que.push(q[i].val);
}
else
{
ans+=q[i].val;
que.push(q[i].val);
ans-=que.top();
que.pop();
}
}
printf("%lld\n",ans);
return 0;
}
最新文章
- caffe学习系列(3):数据层介绍
- Initialize the Storage Emulator by Using the Command-Line Tool
- Android Launcher 研究学习
- 边工作边刷题:70天一遍leetcode: day 84-2
- 我理解的C++虚函数表
- ubuntu10.4 server 配置VPN 安装pptp无法连接外网解决(转)
- TC Asia Competition
- js 编码问题
- Java IO最详解
- 机器学习之决策树(ID3 、C4.5算法)
- UWP 共享文件——接收者
- 破解附近寝室的Wifi密码
- 浅入深出Vue:环境搭建
- PowerBI更新 - 解决方案架构 - PowerBI Solution Architecture(一图胜万字!)
- Dethe is my Finaunce金融
- Java 8 实战
- Likecloud—吃、吃、吃(P1508)
- 20155232《网络对抗》Exp8 Web基础
- python标准模块(下)
- jQuery中click(),bind(),live()的区别(转)
热门文章
- 使用maven创建项目和cannot change version web module 3.0
- ZOJ 3230 Solving the Problems(数学 优先队列啊)
- Activity左边滑出,右边滑入的动画切换
- 12.怎样自学Struts2发送邮件和验证补充[视频]
- MRUnit测试
- oracle的索引有几种?各有何用途?
- MRP-MD04 中的函数
- hihoCoder 1578 Visiting Peking University 【贪心】 (ACM-ICPC国际大学生程序设计竞赛北京赛区(2017)网络赛)
- HDU 6108 小C的倍数问题 【数学】 (2017";百度之星";程序设计大赛 - 初赛(A))
- 配置webpack中externals来减少打包后vendor.js的体积