CodeForces 371C Hamburgers

Description

做一个汉堡需要B(Bread) S(Sausage) C(Cheese)中的一种或多种，给出一个字符串代表配方，给出已有材料，相应材料商店售价，现有资金，问最多能做多少个汉堡？

题目链接

二分

二分实质：对于暴力枚举的优化

为什么会想到用二分？

1. 若想枚举出所有情况：太多且易遗漏
2. 已知答案必在某个固定区间里（此时遍历耗时则用二分优化）

明确目的：

求

1. 最大值?
2. 最小值？
3. 最大化最小值？
4. 最小化最大值？

三要素：

1. 下界：为了方便，可适当向下调整（求最大值时下界必须实际）
2. 上界：为了方便，可适当向上调整（求最大值时，上界是理想值（白日梦值））
3. bool judge（ll ans）：检查资金是否足够

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

int nb, ns, nc, pb, ps, pc;
int B = 0, C = 0, S = 0;
long long money;

bool judge(long long ans)
{
    long long needb = ans * B - nb;
    long long needs = ans * S - ns;
    long long needc = ans * C - nc;
    if(B == 0 || needb < 0)
        needb = 0;
    if(S == 0 || needs < 0)
        needs = 0;
    if(C == 0 || needc < 0)
        needc = 0;
    long long needpay = pb * needb + ps * needs + pc * needc;
    if(needpay <= money)
        return 1;
    else
        return 0;
}

int main()
{
    string s;
    cin >> s;
    int sz = s.size();
    scanf("%d%d%d%d%d%d", &nb, &ns, &nc, &pb, &ps, &pc);
    cin >> money;
    for(int i = 0; i < sz; ++i)
    {
        if(s[i] == 'B')
            B++;
        else if (s[i] == 'S')
            S++;
        else
            C++;
    }
    long long one = B * pb + S * ps + C * pc;
    long long l =  money / one;
    long long r =  money / one + max(nb, max(ns, nc));
    ///找最大值时上界为 幻想值(白日梦值)
    long long mid;
    while(l < r)
    {
        mid = (l + r + 1) >> 1;
        if(judge(mid))///找最大值(二分明确所找最值)
            l = mid;
        else
            r = mid - 1;
    }
    cout << l << '\n';
    return 0;
}
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

改进：调整上下界

long long one = B * pb + S * ps + C * pc;
    long long l =  money / one;
    long long r =  money / one;
    if(B == 0)
    {
        l += min(ns / S, nc / C);
        r += max(ns / S, nc / C);
    }
    else if(S == 0)
    {
        l += min(nb / B, nc / C);
        r += max(nb / B, nc / C);
    }
    else if(C == 0)
    {
        l += min(nb / B, ns / S);
        r += max(nb / B, ns / S);
    }
    else
    {
        l += min(nb / B, min(ns / S, nc / C));
        r += max(nb / B, max(ns / S, nc / C));
    }
Copy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

如上，之前在找上下界时，执着于缩小范围，导致

1. 忽视了分母为0的情况而RE

2. 遗漏了两种材料都不需要的情况而WA

   后来干脆扩展界线，代码简单还AC了