RPG Protagonist
题意
思路
首先我们可以知道，有可能不能使得重量恰好为p 和f 所以会有浪费 那么浪费多少呢？不容易求解，但是，剑和战斧的数量只有 2e5，还可以知道优先拿重量小的可以多拿，所以我们可以贪心的枚举 p 会拿多少把质量较小的武器(比如是剑) 然后求 f最多可以拿多少把剑(同样是质量小的可以多拿的原因)和战斧 求一个 m a x 即可
注意枚举时要从 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; }
