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

京公网安备 11010502036488号