本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-10 08:16:04

题解：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$ 完笔