kuangbin 专题二十三：二分 尺取 单调栈队列 Hamburgers

题目链接：
传送门

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;string bt;//汉堡字符串
ll nb, ns, nc;//每种材料已有多少个
ll pb, ps, pc;//每种材料的单位价格
ll neb, nes, nec;//当前做一个汉堡所需的材料数
ll mon, ans;//当前钱数，和答案int main() {
    cin >> bt;//输入数据scanf("%lld%lld%lld%lld%lld%lld%lld", &nb, &ns, &nc, &pb, &ps, &pc, &mon);//统计出一个汉堡所需材料的数量for(int i = 0; i < bt.size(); i++) {
    if(bt[i] == 'B') neb++;else if(bt[i] == 'S') nes++;else nec++;}//初始化左右边界ll l = 0, r = (ll)1e13;//二分while(l < r) {
    ll mid = l + r >> 1;//每次更新出所需要花费的钱ll difb = (mid * neb - nb) * pb < 0 ? 0 : (mid * neb - nb) * pb;ll difs = (mid * nes - ns) * ps < 0 ? 0 : (mid * nes - ns) * ps;ll difc = (mid * nec - nc) * pc < 0 ? 0 : (mid * nec - nc) * pc;//比较一下所需的钱是否在预算内if(difb + difs + difc <= mon) ans = mid, l = mid + 1;else r = mid;}//输出答案printf("%lld\n", ans);return 0;
}

这是一道二分的题目，大致的思路如下：
首先统计每个一个汉堡所需的数量并保存下来，存下汉堡三种材料的原有量，单位价格，和当前的总钱数。
接下来就是二分操作了，我们二分时要做的就是二分出我们能做出的最多的汉堡数，大致思路就是每次取中间值，以此作为我们要做的汉堡数量。接着分别算出要想做那么多汉堡，我们需要在三种材料上分别花多少钱，把所需钱数与当前所拥有的钱数对比。如果所需的钱超出预算，则往下二分，否则则往上二分。
接着讲讲一些细节，首先在处理所需的钱数时要注意判断不可能为负数，即最好的情况是现有的材料就可以满足需求（倒贴钱是不可能的），因此在计算到所需材料为负数时（即所需的材料已能满足），要把所需材料重新设为0。r 的话我开到了1E13，因为1E12没过。