假设用方法一生成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; }