JZOJ 3928. 【NOIP2014模拟11.6】射击
2024-09-06 14:53:49
3928. 【NOIP2014模拟11.6】射击 (Standard IO)
Time Limits: 1000 ms Memory Limits: 65536 KB
Description
有问题,找副连,无聊的时候当然也可以找他啦。小W找到了他的叔叔——东厂厂长——宇宙超级无敌老WS yy。他们叔侄两个商量之后决定用弹弓打破社区里的一些窗户,但是弹弓每秒只能彻底打破一扇窗户。而且如果某户窗户的主人回来了的话,他们就不能进行破坏了(不然会死得很惨的)。因为有的人装的玻璃好,有的人装的玻璃差,有的人装的玻璃高,有的人装的玻璃矮,所以你不能要求他们叔侄两个打破不同的窗户获得的快乐值必须相同。现在他们想知道在能活着的情况下能够获得的最大快乐值。
Input
第一行一个正整数n,表示共有n个窗户。
接下来n行,每行两个整数,第一个为窗子的主人回来的时刻(秒),第二个为破坏该窗户所能获得的快乐值。
Output
最大的快乐值。
Sample Input
4
1 19
2 10
1 20
2 15
Sample Output
35
Hint
样例说明:
在第0个时刻,他们选择破坏掉3号窗户,在第1个时刻,因为1号窗户的主人已经回来了,所以不能去破坏1号窗户,只能去破坏2号窗户或4号窗户,显然选择4号窗户。总的快乐值就是20+15=35。
Data Constraint
20%的数据,n<=100。
40%的数据,n<=50000。
100%的数据,n<=200000,快乐值的绝对值不超过32767,时刻非负且小于2^31。
题解
这道题有人说用并查集,但是我觉得用贪心+堆更好理解
记第 i 个窗户时间为 a [ i ] . t ,快乐值为a [ i ] . c
先将时间从小到大排序
然后从头开始加,用小根堆维护已选择的窗户
如果个数没达到当前上限,那就选择
如果个数已经达到了上限,而且当前的 c 大于堆顶元素,那就替换
ps:好久没写堆了,可能有点问题,但是能过
代码
#include<cstdio>
#include<algorithm>
#include<vector>
#define N 200010
using namespace std;
struct point{
long t,c;
}a[N];
vector<point>dui;
bool operator >(point a,point b)
{
return a.c>b.c;
}
bool operator <(point a,point b)
{
return a.c<b.c;
}
bool tmp(point a,point b)
{
if(a.t!=b.t)return a.t<b.t;
else return a>b;
}
void ins(point key)
{ long now;
dui.push_back(key);
for(now=dui.size()-1;now>0&&dui[now>>1]>dui[now];now>>=1)
swap(dui[now],dui[now>>1]);
}
void gai(point key)
{ long now;
bool t;
dui[0]=key;
now=0;
t=true;
while((now<<1)+1<=dui.size()&&t){
t=false;
if(dui[now<<1]<dui[(now<<1)+1]){
if(dui[now]>dui[now<<1]){
swap(dui[now],dui[now<<1]);
now<<=1;
t=true;
}
}else
if(dui[now]>dui[(now<<1)+1]){
swap(dui[now],dui[(now<<1)+1]);
now=(now<<1)+1;
t=true;
}
}
}
int main()
{ long n,i,ans=0;
scanf("%ld",&n);
for(i=1;i<=n;i++)
scanf("%ld%ld",&a[i].t,&a[i].c);
sort(a+1,a+n+1,tmp);
for(i=1;i<=n;i++)if(a[i].t!=0){
if(dui.size()<a[i].t&&a[i].c>0)
ins(a[i]);
else if(a[i].c>dui[0].c)
gai(a[i]);
}
for(i=0;i<dui.size();i++)
ans+=dui[i].c;
printf("%ld\n",ans);
return 0;
}
最新文章
- [LeetCode] Range Sum Query 2D - Mutable 二维区域和检索 - 可变
- Set集合
- org.springframework.web.servlet.PageNotFound - No mapping found for HTTP request with URI [XXX] in DispatcherServlet with name &#39;springMVC&#39;
- 滚动变色的文字js特效
- 要慎用mysql的enum字段的原因
- 34988 Happy Reversal(二进制去取反)
- PHP面试出场率较高的题目<;转载>;
- asp.net接收ajax请求参数时为空的现象
- Tomcat 6 --- 你很少使用的安全管理SecurityManager
- xtrabackup之Innobackupex全备恢复
- SPOJ 3643 /BNUOJ 21860 Traffic Network
- java 访问器方法中对象引用的问题
- POJ 3672 Long Distance Racing (模拟)
- vim纯文本处理插件txtbrowser
- 初学laravel框架,解决访问路由404的问题
- mybatis通用mapper的使用
- THUWC2019 GG记
- 课程五(Sequence Models),第一 周(Recurrent Neural Networks) —— 1.Programming assignments:Building a recurrent neural network - step by step
- 【LOJ】#6432. 「PKUSC2018」真实排名
- Silverlight自定义控件系列 – TreeView (4) 缩进