B. RPG Protagonist
题意
两个人偷武器 a只能拿最多p重量的物品,b只能拿最多f重量的物品
现在有重s的剑cnts把,重w的斧cntw把,问两个人最多带走几件物品
题解
对于最后的答案 其中一人先拿则尽量拿 ,拿到装不下
而另一个人则从剩下的东西中优先取出轻的物品,拿完了再拿另外一种物品
按照高中的线性规划知识,a取出ps把剑和pw把斧一定在ps×s+pw×w<=p的线上,由于是离散点
选择枚举取a拿ps把剑后取出尽量多的斧。然后再贪心的让另一个人取更轻的物品，然后更新最终答案
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)
const ll Max=3e4+5;
const double Pi=acos(-1);
int main() {
Turnoff;
int t;cin>>t;
while(t--){
ll p,f;cin>>p>>f;
ll cnts,cntw;cin>>cnts>>cntw;
ll s,w,ans=0;cin>>s>>w;
for(int ps=0;ps<=cnts;ps++){
if(ps*s>p)break;
int pw=min(cntw,(p-ps*s)/w),fs,fw;
if(s<w){
fs=min(cnts-ps,f/s);
fw=min(cntw-pw,(f-fs*s)/w);
}
else{
fw=min(cntw-pw,f/w);
fs=min(cnts-ps,(f-fw*w)/s);
}
ans=max(ans,1ll*fw+fs+ps+pw);
}
cout<<ans<<endl;
}
}
|