RPG Protagonist
题意
一个人和他的追随者 分别可以携带重量为 p p p f f f 的物体
每把剑重 s s s 每个战斧重 w w w 有 c n t s cnt_s cnts 把剑 c n t w cnt_w cntw 把战斧
问 两个人最多能带走多少件武器
思路
首先我们可以知道,有可能不能使得重量恰好为 p p p 和 f f f 所以会有浪费 那么浪费多少呢?不容易求解,但是,剑和战斧的数量只有 2 e 5 2e5 2e5,还可以知道优先拿重量小的可以多拿,所以我们可以贪心的枚举 p p p 会拿多少把质量较小的武器(比如是剑) 然后求 f f f 最多可以拿多少把剑(同样是质量小的可以多拿的原因)和战斧 求一个 m a x max max 即可
注意枚举时要从 0 0 0 开始
代码
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define mod 998244353
#define IOS ios::sync_with_stdio(false)
#define endl '\n'
using namespace std;
typedef long long LL;
LL p, f, cnts, cntw, s, w;
void solve() {
cin >> p >> f >> cnts >> cntw >> s >> w;
if (s > w) {
swap(s, w);
swap(cnts, cntw);
}
LL res = 0;
for (int i = 0; i <= cnts; ++i) { //枚举p拿多少个s
LL t = 0;
if (i * s <= p) {
t += i; //p拿s的数量
t += (p - i * s) / w; //p拿完s后还能拿多少w
}
LL tag; //p拿s的数量
if (!t)
tag = 0;
else tag = i;
LL sum = min(f / s, cnts - tag);
t += sum; //p拿完后 f能拿多少个s
t += min((f - sum * s) / w, cntw - (p - i * s) / w); //f拿完s后能拿多少w
res = max(res, t);
}
cout << res << endl;
}
int main(){
int t; cin >> t;
while(t--)
solve();
return 0;
}