装备合成

题目描述

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

输入描述:

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

输出描述:

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

三分法求极值

三分法用来求单峰函数（或者单谷函数）的极值，它们拥有唯一的极大值点，在极大值点两侧侧严格单调。我们可以在函数区间上任取两个点与，把函数分为三段。
1.若，则与 要么同时处于极大值点左侧,要么处于极大值点两侧。无论哪种情况下，极大值点都在右边，可令。
2.同理，若，则极大值点一定在左侧，可令。

对于本题，我们设制作了件装备1，那么装备二的个数就为,我简单(随便瞎画)了和函数的大致样式，不是很准确，可以想象出其大致趋势是一个单峰函数。下面我们用三分法求解即可。

由于其极大值很有可能是一个实数，为了切合实际，我们并不求出此函数的极大值，而是确定一个范围，在这个范围里去找结果。

完整代码:

#include<bits/stdc++.h>
using namespace std;
int x,y;
int calc(int n){
    return n+min((x-2*n)/4,y-3*n);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&x,&y);
        int l=0,r=min(x/2,y/3);
        while(r-l>5){
            int lmid=l+(r-l)/3,rmid=r-(r-l)/3;
            int lans=calc(lmid),rans=calc(rmid);
            if(lans<rans)l=lmid;
            else r=rmid;
        }
        int sum=0;
        for(int i=l;i<=r;++i){
            sum=max(sum,calc(i));
        }
        cout<<sum<<endl;
    }
}