牛客练习赛59—C：装备合成
链接：https://ac.nowcoder.com/acm/contest/4743/C
来源：牛客网
牛牛有x{x}x件材料a{a}a和y{y}y件材料b{b}b，用2{2}2件材料a{a}a和3{3}3件材料b{b}b可以合成一件装备，用4{4}4件材料a{a}a和1{1}1件材料b{b}b也可以合成一件装备。牛牛想要最大化合成的装备的数量，于是牛牛找来了你帮忙。
输入描述:
输入包含t{t}t组数据
第一行一个整数t{t}t
接下来t{t}t行每行两个整数x,y{x,y}x,y
输出描述:
每组数据输出一行一个整数表示答案。
示例1
输入
5
4 8
7 6
8 10
100 4555
45465 24124
输出
2
2
3
50
13917
备注:
1<=t<=10000
1<=x,y<=1e9
假设第一种装备合成了m件，那么第二种装备可以合成min((x-2*m)/4,y-3*m)件；那么总共的装备个数就是：m+min((x-2*m)/4,y-3*m)；
可以证明当 (x-2*m)/4<y-3*m 时单增，反之单减；所以是个单峰凸函数；可以对m进行三分；（m的最大值是min(x/2,y/2)）
#include
using namespace std;
typedef long long ll;
int x,y;
int get(int m)
{
return m+min((x-2*m)/4,y-3*m);
}
int main()
{
int n;
cin >>n;
while(n--)
{
cin >>x>>y;
int l=0,r=min(x/2,y/3),m1,m2;
while(lget(m2)) r=m2-1;
else l=m1+1;
}
cout <<get(l)<<endl;
}
}
(到现在还没写过三分，对三分模板是一点都不清楚，看来要补一补了)
作者：lywyqmam
