题解：P10730 [NOISG 2023 Qualification] Burgers

· · 题解

思路是二分。
一开始想的时候，想到了暴力搜索。
因为写这道题的前一天集训练了暴力搜索。
显然数据很大，于是想到了二分, 那么复杂度就大大降低了。
想了很久，以为自己写不出来。
但是看了别人的代码，思路差不多。
用了别人的模版。
第一次发题解，改了很多次，求过。 最后祝大家在全国青少年信息学奥林匹克竞赛取得优异的成绩。

#include <bits/stdc++.h>
using namespace std;
int read(){//快读，增加效率
    int x=0,w=1;
    char ch=0;
    while(ch<'0'||ch>'9'){
        if(ch=='-') w=-1;
        ch = getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    return x*w;
}
long long n;//n种原料
long long x[100001];//不同种类原料的份数
long long a[100001];//第一种汉堡的配方
long long b[100001];//第二种汉堡的配方
long long l=0;//二分答案左结点
long long r=1145141919;//二分答案右结点
long long mid;//二分答案中间值
int main(){
    n=read();//读入原料数量
    for(int i=1;i<=n;i++) x[i]=read();//读入不同种类原料的份数
    for(int i=1;i<=n;i++) a[i]=read();//读入第一种汉堡的配方
    for(int i=1;i<=n;i++) b[i]=read();//读入第二种汉堡的配方
    while(l!=r-1){//二分
        long long minn=0;//把自己设得很小，使得第一次用max函数能被替换掉
        long long maxx=1145141919;//把自己设得很大，使得第一次用min函数能被替换掉
        mid=l+(r-l)/2;//等于(l+r)/2
        bool flag=1;//是否可行
        for(int i=1;i<=n;i++){//循环遍历
            if(a[i]==b[i]){
                if(a[i]*mid>x[i]) flag=0;//材料相同，遍历做i个汉堡，看可不可行
            }
            else if(a[i]<b[i]){
                if(a[i]*mid>x[i]) flag=0;//遍历做i个第一种汉堡，看可不可行
                if(b[i]*mid<=x[i]) continue;//可行
                minn=max(minn,mid-(x[i]-a[i]*mid)/(b[i]-a[i]));//mid-(x[i]-a[i]*mid)/(b[i]-a[i])是最大的转换数量
            }
            else{//b[i]>a[i]
                if(b[i]*mid>x[i]) flag=0;遍历做i个第二种汉堡，看可不可行
                if(a[i]*mid<=x[i]) continue;//可行
                maxx=min(maxx,(x[i]-b[i]*mid)/(a[i]-b[i]));
            }(x[i]-b[i]*mid)/(a[i]-b[i])//是最大的转换数量
        }
        if(flag&&minn<=maxx) l=mid;//如果可行，试着能不能做更多汉堡
        else r=mid;//不可行，做少一点汉堡
    }
    cout<<l;//输出答案
}