两个二分

题目

题目描述：

牛牛有x件材料a和y件材料b，用2件材料a和3件材料b可以合成一件装备，
用4件材料a和1件材料b也可以合成一件装备。
牛牛想要最大化合成的装备的数量，于是牛牛找来了你帮忙。

输入描述：

输入包含t组数据
第一行一个整数t
接下来t行每行两个整数x,y

输出描述：

每组数据输出一行一个整数表示答案。

解析

不难看出，答案具有单调性，当能合成m件装备时也一定能合成[0,m-1]件，所以这题可以用二分，把求值问题转化为验证问题，关键在于如何验证枚举的mid是否满足条件。
对于每mid件装备，假定合成了k件装备1，则合成了mid-k件装备2，根据题意得到如下两个公式：
2k+4(mid-k) <=x ①
3k+ (mid-k) <= y ②
k在[0,mid]的范围内，同样可以二分k的取值，当公式①和公式②同时成立时说明可以合成mid件装备，当公式①不成立时扩大k值，否则缩小k值，不存在k同时满足①、②时说明不能合成mid件装备

AC代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll x,y,l,r,mid;
bool solve(ll a){
    ll l1,r1,mid1;
    l1=0,r1=a;
    while(l1 <= r1){
        mid1=(l1+r1)>>1;
        if((4*a-2*mid1) <= x && (a+2*mid1) <= y)
            return true;
        if((4*a-2*mid1) > x)
            l1=mid1+1;
        else
            r1=mid1-1;
    }
    return false;
}
int main(){
    int t;
    cin>>t;
    while(t--){
        l=0,r=1000000000;
        scanf("%lld%lld",&x,&y);
        while(l <= r){
            mid=(l+r)>>1;
            if(solve(mid))
                l=mid+1;
            else
                r=mid-1;
        }
        cout<<r<<endl;
    }
}