B. RPG Protagonist

题目链接：https://codeforces.com/contest/1400/problem/B

/*两个人容积 p 	f 物品数量  cnts  cntw物品体积  v1    v2问两人最多带走的物品数量思路：假设只有一个人尽量带体积小的，若还有剩余则带体积大的两个人： if   (两人都带体积小的还不能带完) 那么只带体积小的，带体积大的也浪费空间 else  两人必须把体积小的都带完，带小的肯定比大的省空间 (证明：假设不把小的带完，而带了大的是最优结果，我们一定可以把那个体积大的换成小的这样数量不变，但剩余空间变大了) 解决：对于else 情况，我们枚举p带体积小的数目从(0~cnts),进而f带体积小的数目从(cnts~0)求这个过程的最大值 
*/

#include
#include
#include
using namespace std;
int cnts, cntw;
int v1,  v2; 
int p,f;int main(){int T;scanf("%d",&T);while(T--){int ans=0;scanf("%d%d",&p,&f);scanf("%d%d",&cnts,&cntw);scanf("%d%d",&v1,&v2);if(v1>v2){swap(v1,v2);swap(cnts,cntw);	} int cnt=p/v1+f/v1;if(cnt<=cnts){printf("%d\n",cnt);}else{int x1,y1, x2,y2;for(int i=0;i<=cnts;i++){x1=i;if(p-v1*i<0) break; x2=(p-v1*i)/v2;int temp=f-(cnts-x1)*v1;if(temp<0) continue;y1=cnts-x1;y2=min(cntw-x2,temp/v2);ans=max(ans,x1+x2+y1+y2);}printf("%d\n",ans);}	}
}/*
1
33 27
6 10
5 6
*/

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！