P9124 [USACO23FEB] Bakery S 题解 | 面包店 | 推一推不等式
_Cheems
·
·
题解
题目简介
有 n 个人来买两种东西，要使 a_i \times t_c +b_i \times t_m \leq c_i ，你可用一块钱减少 t_c 或 t_m 一个单位时间，但不能减到零。
求最少要花费多少钱，才能使上式成立。
思路
假设操作后，tc 减去 x，tm 减去 y，答案就是 x+y。
很容易想到二分，那么二分什么呢？
二分 x（或 y）吗？不对，不具有单调性，因为还可以调整 y。可能把 x 调大点，y 调小点，说不定更优？
但 x+y 一定具有单调性，显而易见。于是问题变为了检验正确性。
怎么检验啊？设 mid = x+y，推下不等式呗。
拆括号得：
$ a \times t_c-a \times x+b \times t_m-b \times mid+b \times x≤c $。
下一步怎么搞？不妨试试：移项把 $a$ 和 $b$ 凑在一起。
$ b \times x-a \times x≤c-a \times t_c-b \times t_m+b \times mid $。
即：
$ (b-a) \times x≤c-a \times t_c-b \times t_m+b \times mid $。
为了方便，设：
$ k = c-a \times t_c-b \times t_m+ b \times mid $。
于是就能对 $a-b$ 的取值分类讨论啦。
- 若 $a-b>0$：原式不变，$x \leq \frac{k}{a-b}$，向下取值（ floor ）。
- 若 $a-b=0$：若$k<0$，则无解。
- 若 $a-b<0$：变号即可，$x ≥ \frac{k}{a-b}$，向上取值（ ceil ）。
最终会得到一大堆与 $x$ 有关的大小关系式，判断是否有解即可。
关于上下界：
设 $mi \leq x \leq ma$。
- 对于 $mi$：可以一个不减。但如果另一个数没法再减了，则必须要减它了，另一个数可以减去 $y-1$ 次，因此取 $0$ 和 $mid-t_m+1$ 的最大值。
- 对于 $ma$：至多把 $t_c$ 减到 $1$，不过 $mid$ 得够大，因此取 $ t_c-1$ 和 $mid$ 的最小值。
### 代码
```cpp
#include<bits/stdc++.h>
using namespace std;
long long t,n,mid,tic,tim,a[105],b[105],c[105],l,r;
long long dan()
{
long long mi,ma;
ma=min(tic-1,mid);
mi=max((long long)(0),mid-tim+1);
for(long long i=1; i<=n;i++)
{
long long k=c[i]-a[i]*tic-b[i]*tim+b[i]*mid;
if(a[i]==b[i]&&k<0) return 0;
if(b[i]-a[i]>0) ma=min(ma,(long long)floor(k*1.0/(b[i]-a[i])));
if(b[i]-a[i]<0) mi=max(mi,(long long)ceil(k*1.0/(b[i]-a[i])));
}
return mi<=ma;
}
int main()
{
cin>>t;
while(t--)
{
scanf("%lld%lld%lld",&n,&tic,&tim);
for(long long i=1; i<=n;i++)
{
scanf("%ld%lld%lld",&a[i],&b[i],&c[i]);
}
l=-1,r=tic+tim-1;
while(l+1<r)
{
mid=(l+r)/2;
if(dan()) r=mid;
else l=mid;
}
cout<<r<<endl;
}
return 0;
}
```