CodeForces - 371C (Hamburgers) 做题笔记 发表于 2018-07-09 | 更新于 2020-07-30 | | 阅读次数: 题目链接:http://codeforces.com/problemset/problem/371/C 这题一开始用的贪心,但WA掉了。正解是二分一个答案,查看能否用现有的钱买到相应的食材。 12345678910111213141516171819202122232425262728293031323334353637383940414243#include <bits/stdc++.h>using namespace std;typedef long long LL;char s[200];LL ca, cb, cc;LL na, nb, nc;LL pa, pb, pc;LL r;bool check(LL x) { LL need = 0; LL cnta = x * ca - na; if(ca > 0 && cnta > 0) need += cnta * pa; LL cntb = x * cb - nb; if(cb > 0 && cntb > 0) need += cntb * pb; LL cntc = x * cc - nc; if(cc > 0 && cntc > 0) need += cntc * pc; if(need > r) return false; else return true;}int main() { scanf("%s%*c", s); cin >> na >> nb >> nc; cin >> pa >> pb >> pc; cin >> r; ca = cb = cc = 0LL; for(int i = 0; s[i] != '\0'; i++) { switch(s[i]) { case 'B': ca++; break; case 'S': cb++; break; case 'C': cc++; break; } } LL l = 0, r = 1100000000009LL; while(l < r) { LL mid = (l + r + 1) >> 1; if(check(mid)) l = mid; else r = mid - 1; } cout << r; return 0;}