自动搬运

查看原文

来自洛谷，原作者为

	rhn7 洛谷用户数：1789309

搬运于2025-08-24 23:00:43，当前版本为作者最后更新于2024-10-05 19:32:31，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

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

$xa_i+yb_i \le x_i$

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

$xa_i+(t-x)b_i \le x_i$

$xa_i+tb_i-xb_i \le x_i$

$x(a_i-b_i) \le x_i-tb_i$

若 $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;
}