CodeForces - 1400B - RPG Protagonist (贪心)

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;
}
上一篇:leetcode每日一题之3.至少有 K 个重复字符的最长子串


下一篇:git submodule 多项目操作管理 - 知乎