自动搬运

查看原文

来自洛谷，原作者为

	MiPloRAs_3316 けっしょうばん 可爱捏 ⎛⎝≥⏝⏝≤⎛⎝ || 我哀

搬运于2025-08-24 22:45:34，当前版本为作者最后更新于2023-04-17 14:12:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目传送门 | 珂能更好的食用体验

题意概述

• 奶牛需要为 TA 的 $n$ 个朋友制作糕点（$a_i$ 个 $A$ 和 $b_i$ 个 $B$）。每个朋友最多等待 $c_i$ 个单位时间，如果没有拿到糕点，TA 就会伤心地离开。
• 制作 $1$ 个 $A$ 需要 $t_c$ 个单位时间，制作 $1$ 个 $B$ 需要 $t_m$ 个单位时间。
• 奶牛可以花费 ￥$1$ 去升级 TA 的烤箱。升级后，可以少花 $1$ 个单位时间来生产 $1$ 个 $A$ 或少花 $1$ 个单位时间来生产 $1$ 个 $B$。
• 求出她必须花费的最少的 money，以便她的面包店能够满足所有朋友的需求。

---

解题思路

我们可以先假设对于第 $i$ 个朋友（订单），需要升级 $x$ 次 $A$ 烤箱， $y$ 次 $B$ 烤箱。

于是，显而易见的：（看起来很简洁但一点都不好解）

$$a_i \times (t_c-x) + b_i \times (t_m-y) \leqslant c_i $$

令 $mid=x+y$，于是：

$$a_i \times t_c-a_i \times x+b_i \times t_m - b_i \times mid+b_i \times x \leqslant c_i $$$$\therefore (b_i-a_i)\times x \leqslant c_i-a_i \times t_c-b_i\times t_m+b_i\times mid $$

令 $k_i=c_i-a_i \times t_c-b_i\times t_m+b_i\times mid$，

所以，就可以根据上述不等式进行二分答案了。（二分的当然是 $x+y$。）

接下来，浅浅说一下不等式的解集：

$$\begin{cases}x=\varnothing, &b_i-a_i=0 \\ x\leqslant \dfrac{k_i}{b_i-a_i} , &b_i-a_i>0\\ x\geqslant \dfrac{k_i}{b_i-a_i} , &b_i-a_i<0\end{cases} $$

上述第 $2$ 个式子用于锁定解集的上限，第 $3$ 个式子用于锁定解集的下限。

同时，$x$ 与 $y$ 的值应该为整数。所以为了便于大家理解程序，解集应该写成下面这个亚子。

$$\begin{cases}x=\varnothing, &b_i-a_i=0 \\\\ x\leqslant \left\lfloor\dfrac{k_i}{b_i-a_i}\right\rfloor , &b_i-a_i>0\\\\ x\geqslant \left\lceil\dfrac{k_i}{b_i-a_i}\right\rceil, &b_i-a_i<0\end{cases} $$

---

Code

#include<bits/stdc++.h>
using namespace std;
long long T,n,tc,tM,a[110],b[110],c[110];
bool check(long long x)
{
	long long maxx=min(tc-1,x);
	long long minn=max(0LL,x-tM+1);
	for(int i=1; i<=n; i++)
	{
		long long k=c[i]-a[i]*tc-b[i]*tM+b[i]*x;
		if(b[i]-a[i]==0)
		{	
			if(k<0) return false;
		}
		else if(b[i]-a[i]>0) maxx=min(maxx,(long long)floor(k*1.0/(b[i]-a[i])));//二式
		else minn=max(minn,(long long)ceil(k*1.0/(b[i]-a[i])));//三式
	}
	return maxx>=minn;//判断是否有解
}
int main()
{
	for(cin>>T;T;T--)
	{
		cin>>n>>tc>>tM;
		for(int i=1; i<=n; i++)
			cin>>a[i]>>b[i]>>c[i];
		long long l=-1,r=tc+tM-1;
		while(l+1<r)//简单的二分答案
		{
			long long mid=l+r>>1;
			if(check(mid)) r=mid;
			else l=mid;
		}
		cout<<r<<endl;
	}
	return 0;
}