ACM - 牛客4743C - 三分

题目链接

题意：中文题

思路：
三分。
对于（a，b），不妨设：A=2a+3b，B=4a+b
对于A装备来说，要想越多，那么消耗的b就很快。
对于B装备来说，要想越多，那么消耗的a就很快。
对于总数来说，A+B，那么一定存在“合理”分配，使得a和b的消耗比较平均。这个“合理”的方案，就是最大值，也就是三分中的极大值。
所以，用函数图像思考：
在左边，函数递增；在右边，函数递减。函数有极大值。

边界条件：
考虑：calc(ml) <= calc(mr)
首先注意这里一定带有等号，如果弄成 >= ，也一样

由于 ml 的函数值小，我们要求的是极大值，那么意味着，在[l,ml]的区间内，一定比 mr 的点小了，可以删去该区间，l = ml + 1
反之，同理

如果是求极小值，判断一致，赋值相反。代码如下。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
ll x,y;

ll calc(ll xx){
    return xx + min((x - 2 * xx) / 4, (y - 3 * xx));
}

int main(){
    //freopen("input.txt", "r", stdin);
    int T;
    scanf("%d", &T);
    while(T--){
        scanf("%lld%lld", &x, &y);
        ll l = 0, r = min(x / 2, y / 3), ans = 0;
        ll tmp, ml, mr, mlans, mrans;
        while(l <= r){
            tmp = (r - l) / 3;
            ml = l + tmp;
            mr = r - tmp;
            mlans = calc(ml);
            mrans = calc(mr);
            if (mlans <= mrans){
                ans = max(ans, mlans);
                l = ml + 1;
            }
            else{
                ans = max(ans, mrans);
                r = mr - 1;
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

补充一下：
有dalao的写法是这样，其实更合理：

while(l + 10 <= r){
    ...
}
for(int tmp = l; tmp <= r; tmp++){...}

这样可以解决，这个函数不是完全单调递增的情况。
比如出现，3，3,4,4,4,4,5,5,5,6,5,5,5,5,4,4,1
这样的话，6一定会被算到。
这个10，相当于是最后选取了一个包含极大值的区间，然后每个计算。