题解：P10730 [NOISG 2023 Qualification] Burgers

rhn7 · 2024-10-05 19:32:31 · 题解

模拟赛时忘写上取整 100->50，警示后人。

贪心、枚举都不行，但我们发现答案有单调性，尝试一下二分。

设第一个汉堡买了 x 个，第二个汉堡买了 y 个，要 check 的答案为 t，得到不等式：

显然 x+y=t，所以 y=t-x。

若 a_i=b_i，x_i<tb_i 时无解，否则 x 取任意值。

若 a_i>b_i，x \le \frac{(x_i-tb_i)}{a_i-b_i}

若 a_i<b_i，x \ge \frac{(x_i-tb_i)}{a_i-b_i}

最后看不等式组是否冲突即可，且 x 必须是 [0,t] 中的正整数。

#include<bits/stdc++.h>
#define rd(x) scanf("%lld",&x)
using namespace std;
typedef long long ll;
const ll N=1e5+5;
ll n,x[N],a[N],b[N];
bool chk(ll mid){
    ll l=0,r=1e18;
    for(ll i=1;i<=n;i++){
        if(a[i]==b[i]){
            if(mid*b[i]>x[i]) return 0;
        }else if(a[i]>b[i]){
            if(mid*b[i]>x[i]) return 0;
            r=min(r,(x[i]-mid*b[i])/(a[i]-b[i]));
        }else{
            l=max(l,(mid*b[i]-x[i]+b[i]-a[i]-1)/(b[i]-a[i]));
        }
    }
    if(l>r||r<0||l>mid) return 0;
    return 1;
}
int main(){
    rd(n);
    for(ll i=1;i<=n;i++) rd(x[i]);
    for(ll i=1;i<=n;i++) rd(a[i]);
    for(ll i=1;i<=n;i++) rd(b[i]);
    ll l=0,r=5e9,ans;
    while(l<=r){
        ll mid=(l+r)>>1;
        if(chk(mid)) ans=mid,l=mid+1;
        else r=mid-1;
    }
    cout<<ans;
    return 0;
}