首页 > 代码库 > Codeforce 371C Hamburgers (二分答案)

Codeforce 371C Hamburgers (二分答案)

题目链接 Hamburgers

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

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 #define REP(i,n) for(int i(0); i <  (n); ++i)
 6 #define LL       long long
 7 
 8 char str[1010];
 9 LL len;
10 LL b, c, s, nb, nc, ns, pb, pc, ps;
11 LL money;
12 
13 bool judge(LL x){
14     LL mb = x * b;
15     LL ms = x * s;
16     LL mc = x * c;
17 
18     LL now_money = money;
19     if (mb > nb) now_money -= (mb - nb) * pb;
20     if (ms > ns) now_money -= (ms - ns) * ps;
21     if (mc > nc) now_money -= (mc - nc) * pc;
22 
23     return now_money >= 0LL;
24 }
25 
26 int main(){
27 
28     scanf("%s", str);
29     len = strlen(str);
30     REP(i, len){
31         if (str[i] == B) ++b;
32         else if (str[i] == S) ++s;
33         else ++c;
34     }
35 
36     cin >> nb >> ns >> nc;
37     cin >> pb >> ps >> pc;
38     cin >> money;
39 
40     LL l = 0, r = 1e14;
41     while (l + 1 < r){
42         LL mid = (l + r) / 2;
43         if (judge(mid)) l = mid; else r = mid - 1;
44     }
45 
46     if (judge(r)) cout << r << endl; else cout << l << endl;
47     return 0;
48 
49 }

 

Codeforce 371C Hamburgers (二分答案)