假设用方法一生成n件,那么方法二就是
总件数all=n+min((x-2n)/4,y-3n),求all的最大值
一般的就是把n枚举,但是从题目x,y<=1e9
n=[0,min(x/2,y/3)]——即完全不用方法一 ->完全用方法一,时间复杂度是1e9/2
所以我们要用三分缩小n的范围,然后在范围内枚举n
把all看出是关于自变量n的函数,all=n+min((x-2n)/4,y-3n),
三分用之前一定要验证函数是或单增或单减的函数,即h(x)'在范围内最多一个零点
样例打表发现本函数为单增的函数
每次看两个三分之一点哪个更小,更小的更新为边界

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

int t,x,y,l,r,ans,m1,m2;

int fct(int n){
    return n+min((x-2*n)/4,y-3*n);
}
int main(){
    cin>>t;
    for(int i=0;i<t;i++){
        cin>>x>>y;
        l=0,r=min(x/2,y/3);

        while(r-l>10){
            m1=l+(r-l)/3, m2=r-(r-l)/3;
            if(fct(m1)>fct(m2)) r=m2;
            else l=m1;
        }
        ans=0;
        for(int i=l;i<=r;i++){
            ans=max(ans,fct(i));
        }
        cout<<ans<<endl;
    }
    return 0;
}

打表代码
#include<bits/stdc++.h>
using namespace std;

int t,x,y,l,r,ans,m1,m2;
int cnt,flag;

int fct(int n){
    return n+min((x-2*n)/4,y-3*n);
}
int main(){
    for(int x=1;x<1000;x++){
        for(int j=1;y<1000;y++){
            cnt=0;
            flag=fct(1)-fct(0);
            for(int i=1;i<=min(x/2,y/3);i++){
                flag*=fct(i)-fct(i-1);
                if(flag<0) cnt++;
                flag=fct(i)-fct(i-1);
            }
            cout<<cnt<<endl;
        }
    }
    return 0;
}