Luogu P4823 [TJOI2013]拯救小矮人
2024-10-07 04:01:08
题目
\(n^2\)的dp已经成为辣鸡做法了,%%%wch。
首先一个结论:\(a+b\)小的人在上。
这个东西我们有三种方法解决证明:
1、感性理解,\(a+b\)越大的人逃生能力越强,放在下面就越可能溜。
2、交换法。
3、找别的博客。
所以我们排个序确定顺序,然后来考虑如何计算最多能跑多少人。
然后我们记录高度的后缀和\(s_i\),从上到下到第\(i\)个人时前面出不去的人的高度\(t\)。
如果第\(i\)个人能直接出去即\(t+s_i+b_i\),那么让他直接溜。
如果出不去,并且把溜出去了的最高的人拉下来能够让他出去,并且溜出去了的最高的人比这个人高,我们就把溜出去了的最高的人拉下来,让这个人出去。
否则这个人就走不了了。
对于第二个操作,开个堆维护就好了。
考虑第二个操作的正确性:这个操作不会影响当前出去的人数,并且垫底的高度\(t\)一定会增加,后面的人就一定更容易出去。
而所有拉更多人下来的举动都可以归纳到拉一个人下来中。
#include<bits/stdc++.h>
using namespace std;
const int N=2007;
int s[N];
priority_queue<int>q;
struct node{int a,b;}p[N];
int operator<(node a,node b){return a.a+a.b<b.a+b.b;}
int read(){int x;scanf("%d",&x);return x;}
int main()
{
int n=read(),i,h,t=0,ans=0;
for(i=1;i<=n;++i) p[i].a=read(),p[i].b=read();
sort(p+1,p+n+1),h=read();
for(i=n;i;--i) s[i]=s[i+1]+p[i].a;
for(i=1;i<=n;++i)
if(s[i]+p[i].b+t>=h) q.push(p[i].a),++ans;
else if(!q.empty()&&p[i].a<q.top()&&q.top()+s[i]+p[i].b+t>=h) t+=q.top(),q.pop(),q.push(p[i].a);
else t+=p[i].a;
return !printf("%d",ans);
}
最新文章
- IOS开发之显示微博表情
- SpringMVC接收Post的实体/JSon数据
- C++设计模式-Proxy代理模式
- C++ 创建和遍历二叉树
- discourse 基于ember.js+rails项目的安装部署
- Collection的toArray()使用上需要注意的地方
- Physicals
- 关于IIS中WEB网站访问弹“验证输入框”及“401限制访问”的解决办法
- ASP.NET页面生命周期总结(2)
- Ubuntu下开发环境搭建
- noi 1.8 11图像旋转
- vueJs 源码解析 (三) 具体代码
- 浅谈TCP IP协议栈(二)IP地址
- if __name__ == &#39;__main__&#39; 这段代码怎么理解???
- mysql之工具的使用总结(mac版本)
- CCF WC2017 &; THU WC2017 旅游记
- 浅谈 WebDriver如何应对不同浏览器
- pytroch 0.3 到 0.4版本迁移资料mark
- textarea自动增长宽高
- 第154天:canvas基础(一)