题解 | #装备合成#
装备合成
https://ac.nowcoder.com/acm/problem/200211
思路:
三分,三分要满足函数是先增后减或者先减后增的,这里可以三分用第一个方案的次数,假设第一个方案用了n次,那么第二个方案的个数就是min( (x-2n)/4 , y-3n ),对于单调性的证明,参考下面的博客。
代码:
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
int x,y;
int check(int f){
return f+min((x-f*2)/4,(y-3*f));//总件数
}
int main() {
int t;
cin>>t;
while(t--)
{
scanf("%d%d",&x,&y);
int l=0,r=min(x/2,y/3);//r最大就是都用第一种方案
while(l<r)
{
int mid1=l+(r-l)/3;
int mid2=r-(r-l)/3;
if(check(mid1)>check(mid2))
{
r=mid2-1;
}
else l=mid1+1;
}
cout<<check(l)<<endl;
}
return 0;
}