[luogu] P4823 [TJOI2013]拯救小矮人(贪心)
2024-10-01 11:22:39
P4823 [TJOI2013]拯救小矮人
题目描述
一群小矮人掉进了一个很深的陷阱里,由于太矮爬不上来,于是他们决定搭一个人梯。即:一个小矮人站在另一小矮人的 肩膀上,知道最顶端的小矮人伸直胳膊可以碰到陷阱口。
对于每一个小矮人,我们知道他从脚到肩膀的高度Ai,并且他的胳膊长度为Bi。陷阱深度为H。
如果我 们利用矮人1,矮人2,矮人3,。。。矮人k搭一个梯子,满足A1+A2+A3+....+Ak+Bk>=H,那么矮人k就可以离开陷阱逃跑了,一 旦一个矮人逃跑了,他就不能再搭人梯了。
我们希望尽可能多的小矮人逃跑, 问最多可以使多少个小矮人逃跑。
输入输出格式
输入格式:
第一行一个整数N, 表示矮人的个数,接下来N行每一行两个整数Ai和Bi,最后一行是H。(Ai,Bi,H<=10^5)
输出格式:
一个整数表示对多可以逃跑多少小矮人
输入输出样例
输入样例#1: 复制
2
20 10
5 5
30
输出样例#1: 复制
2
输入样例#2: 复制
2
20 10
5 5
35
输出样例#2: 复制
1
说明
30%的数据 N<=200
100%的数据 N<=2000
题解
有一个很巧妙的贪心排序。
对于
1.手长脚长,那么可以留下来先辅助逃跑。
2.手长脚短,那么可以后面逃跑,先垫着。
3.手短脚长,那么就是为了让别人跑的。
所以,我们按照\(a.a+a.b<b.a+b.b\)排序,
但是接下来怎么贪心呢,我们跑背包。
背包的设置很巧妙,我们以累计身高为值,\(f[i]\)表示当前跑出的人数,如果当前\(f[i]\)可以跑出去,就转移身高,即正值就更新答案。
个人感觉这个贪心其实并不好想。
Code
#include<bits/stdc++.h>
using namespace std;
int f[5001],ans,n,h;
struct node{
int a,b;
}a[5001];
bool cmp(node a,node b){return a.a+a.b<b.b+b.a;}
int read(){
int x=0,w=1;char ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
return x*w;
}
int main(){
n=read();
memset(f,128,sizeof(f));f[0]=0;
for(int i=1;i<=n;i++){
a[i].a=read();a[i].b=read();f[0]+=a[i].a;
}h=read();
sort(a+1,a+n+1,cmp);
for(int i=1;i<=n;i++){
for(int j=i;j>=1;j--){
if(f[j-1]+a[i].b>=h)f[j]=max(f[j],f[j-1]-a[i].a);
}
}
for(int i=0;i<=n;i++)
if(f[i]>=0)ans=i;
cout<<ans<<endl;
return 0;
}
最新文章
- 使用 Vue 2.0 实现服务端渲染的 HackerNews
- 原生andriod浏览器回退后dom(click)事件全体失效问题探究
- ES6新特性:Function函数扩展, 扩展到看不懂
- Sql中的并(UNION)、交(INTERSECT)、差(minus)、除去(EXCEPT)详解
- Android Studio 生成Jar包时遇到的gradlew下载问题
- iOS红马甲项目开发过程Bug总结(1)
- 经典的SQL面试题
- 组合数(codevs 1631)
- OpenCV中Mat的详解
- IOS 开发 【序】
- WebService--使用 CXF 开发 REST 服务
- WINDOWS 2012忘记密码之后。。。
- tcp接收xml数据解析
- Java没有源代码的同步集合~
- 团队作业8----第二次项目冲刺(Beta阶段) 第一天
- libcoro:在c++中支持coroutine
- mysql创建新的用户及flush privileges解析
- sqlmap-学习1 配置环境
- iOS开发线程安全问题
- css 纸张效果 666