题解：P10730 [NOISG 2023 Qualification] Burgers

· · 题解

题解：P10730

前言

题目传送门

博客食用更佳

本题解借鉴了部分楼上大佬的内容，但是我想详细讲一下赚点估值，以便理解（楼上的题解我看了两天才看懂）。

题意

两种汉堡，一个汉堡对于原料 x_i 需要使用 a_i 或 b_i 份（根据汉堡是哪种决定使用份数），求最大能做的汉堡个数。

思路

首先想到贪心，很明显，贪心是错的。因为你在选择原料时并不知道是优先选哪个汉堡，也不知道每种汉堡要选多少个。
其次想到 DP。如此你会发现，转移方程不知道怎么写，而且时间会超。

我们发现，对于一个整数 k,如果可以做成 k 个汉堡，那么也一定能做出数量小于 k 的汉堡；反之，如果 k 个汉堡不可做，那么数量大于 k 的汉堡也一定不可做——这不就是单调性嘛！
有了单调性，下意识想到二分。可是难题又来了：我们的 check 函数怎么写呢？

我们发现，如果 a_i 比 b_i 小并且在 x_i 范围内能够取到 k 个汉堡的话，会对 a_i 有一个下界要求：总量为 k 个汉堡，a_i 取到的越少 b_i 取到的就越多（废话），这样用到的原料总数就会更多，就有可能超出 x_i 的范围。所以要求 a_i 至少要取到多少个才能使汉堡总数达到 k（在 x_i 范围内），这便是 a_i 的下界要求。
同理，当 b_i<a_i 时，对 b_i 有也一个下界要求，我们可以转换为对 a_i 的上界要求。

在 a 的上下界中去选，如图，红色为上界，蓝色为下界，如果上下界不相交（最大下界小于等于最小上界），即存在 a 的一个取值，满足它大于等于所有下界且小于等于所有上界，那么便可以取到 k 个汉堡，check 函数返回值为 true。

袋马

与楼上大佬大差不差（感觉我的更简洁），注释请看楼上

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F(i,l,r) for(int i = l;i <= r;i++)
const int N = 1e6 + 50,M = 1e3 + 50;
const int INF = 0x3f3f3f3f3f3f3f3f,INT = 0x7fffffff;
const int mod = 1e9 + 7;

int n,x[N],a[N],b[N];

inline bool check(int k){
    int mi=0,ma=1e9;
    //上界和下界
    F(i,1,n){
        if(a[i]==b[i]){
            if(a[i]*k>x[i]) return 0;
        }else if(a[i]<b[i]){
            if(a[i]*k>x[i]) return 0;
            if(b[i]*k<=x[i]) continue;
            mi=max(mi,k-(x[i]-a[i]*k)/(b[i]-a[i]));
//          a[i]的下界
        }else{
            if(b[i]*k>x[i]) return 0;
            if(a[i]*k<=x[i]) continue;
            ma=min(ma,(x[i]-b[i]*k)/(a[i]-b[i]));
        }
    }
    return (mi <= ma);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    cin>>n;
    F(i,1,n) cin>>x[i];
    F(i,1,n) cin>>a[i];
    F(i,1,n) cin>>b[i];
    int l=0,r=1e9;
    while(l<=r){
        int mid = (l+r) >>1;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<r;

    return 0;
}

AC记录

——2024.9.10,9:10 完笔