Codeforces 371C Hamburgers (二分答案)

时间:2022-12-19 16:32:52

题目链接 Hamburgers

二分答案,贪心判断即可。

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int i(0); i <  (n); ++i)
#define LL       long long

char str[1010];
LL len;
LL b, c, s, nb, nc, ns, pb, pc, ps;
LL money;

bool judge(LL x){
    LL mb = x * b;
    LL ms = x * s;
    LL mc = x * c;

    LL now_money = money;
    if (mb > nb) now_money -= (mb - nb) * pb;
    if (ms > ns) now_money -= (ms - ns) * ps;
    if (mc > nc) now_money -= (mc - nc) * pc;

    return now_money >= 0LL;
}

int main(){

    scanf("%s", str);
    len = strlen(str);
    REP(i, len){
        if (str[i] == 'B') ++b;
        else if (str[i] == 'S') ++s;
        else ++c;
    }

    cin >> nb >> ns >> nc;
    cin >> pb >> ps >> pc;
    cin >> money;

    LL l = 0, r = 1e14;
    while (l + 1 < r){
        LL mid = (l + r) / 2;
        if (judge(mid)) l = mid; else r = mid - 1;
    }

    if (judge(r)) cout << r << endl; else cout << l << endl;
    return 0;

}