USACO23FEB-Silver A

题目来源

洛谷： USACO23FEB-Silver Milk Sum(A)

SPOJ：USACO23FEB-Silver Milk Sum(A) - 题面

题解： USACO23FEB-Silver Milk Sum(A) - 题解

题目

题目描述（中文）

$\qquad$Bessie 开了一家面包店!

$\qquad$在她的面包店里，Bessie 有一个烤箱，可以在 $t_C$ 的时间内生产一块饼干或在 $t_M$ 单位时间内生产一块松糕。
$(1 \le t_C,t_M \le 10^9)$。由于空间限制，Bessie 一次只能生产一种糕点，所以要生产 $A$ 块饼干和 $B$ 块松饼，需要 $A\cdot t_C+B\cdot t_M$ 单位的时间。

$\qquad$Bessie的 $N (1\le N\le 100)$ 朋友都想一个一个地去面包店。第 $i$ 个朋友一进门就会点 $a_i(1 \le a_i \le 10^9)$ 块饼干和 $b_i(1 \le b_i \le 10^9)$ 块松饼。Bessie 没有空间来储存糕点，所以她只有在接到订单后才开始制作糕点。此外，Bessie 的朋友都很忙，所以第 $i$ 个朋友只愿意等 $c_i(a_i+b_i \le c_i \le 2 \cdot 10^{18})$ 个单位的时间，然后就伤心地离开。

$\qquad$Bessie 真的不希望她的朋友们伤心，她可以用一块钱升级她的烤箱，让它少花一个单位的时间来生产一块饼干或少花一个单位的时间来生产一个松饼。她不能将她的烤箱升级到花费小于等于 $0$ 的时间，但她可以选择在她的朋友到来之前将她的烤箱升级多少次，只要生产一块饼干和生产一个松饼所需的时间都严格保持为正数。

$\qquad$对于每一个 $T(1\le T\le 100)$ 的测试案例，请帮助 Bessie 找出她必须花费的最小的钱数量，以便她的面包店能够满足所有的朋友。

输入格式

第一行包含 $T$，测试案例的数量。

每个测试用例都以一行开始，包含 $N$,$t_C$,$t_M$。然后，接下来的 $N$ 行各包含三个整数 $a_i,b_i,c_i$。

测试案例用换行符隔开。

输出格式

Bessie 需要为每个测试案例花费的最少钱数，每行一个。

样例 1

样例输入 1

2

3 7 9
4 3 18
2 4 19
1 1 6

5 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 22

样例输出 1

11
6

提示

样例解释 1

$\qquad$在第一个测试案例中，贝西可以支付 $11$ 元来减少 $4$ 单位生产一块饼干所需的 时间和 $7$ 单位生产一块松饼所需的时间，从而使她的烤箱在 $3$ 单位的时间内生产饼干，在 $2$ 单位的时间内生产松饼。那么她可以在 $18$ 单位的时间内满足第一个朋友，在 $14$ 单位的时间内满足第二个朋友，在 $5$ 单位的时间内满足第三个朋友，所以他们都不会伤心而离开。

$\qquad$在第二个测试案例中，贝西应该把生产一块饼干的时间减少 $6$ 单位，把生产一块松饼的时间减少 $0$ 单位。

数据规模与约定

• 输入 $2-4$：$N\le 10,t_C,t_M \le 1000$。
• 输入 $5-11$，没有额外的约束。

题目描述(English)

$\qquad$Bessie has opened a bakery!

$\qquad$In her bakery, Bessie has an oven that can produce a cookie in $t_C$
units of time or a muffin in $t_M$
units of time $(1\le t_C,t_M\le 10^9)$. Due to space constraints, Bessie can only produce one pastry at a time, so to produce $A$ cookies and $B$ muffins, it takes $A \cdot t_C+B \cdot t_M$ units of time.

$\qquad$Bessie’s $N (1\le N\le 100)$ friends would each like to visit the bakery one by one. The $i$-th friend will order $a_i(1 \le a_i \le 10^9)$ cookies and $b_i(1 \le b_i \le 10^9)$ muffins immediately upon entering. Bessie doesn’t have space to store pastries, so she only starts making pastries upon receiving an order. Furthermore, Bessie’s friends are very busy, so the $i$-th friend is only willing to wait $c_i(a_i+b_i \le c_i \le 2 \cdot 10^{18})$ units of time before getting sad and leaving.

$\qquad$Bessie really does not want her friends to be sad. With one mooney, she can upgrade her oven so that it takes one less unit of time to produce a cookie or one less unit of time to produce a muffin. She can’t upgrade her oven a fractional amount of times, but she can choose to upgrade her oven as many times as she needs before her friends arrive, as long as the time needed to produce a cookie and to produce a muffin both remain strictly positive.

$\qquad$For each of $T(1 \le T \le 100)$ test cases, please help Bessie find out the minimum amount of moonies that Bessie must spend so that her bakery can satisfy all of her friends.

输入格式

The first line contains $T$, the number of test cases.

Each test case starts with one line containing $N$
, $t_C$, $t_M$. Then, the next $N$ lines each contain three integers $a_i,b_i,c_i$.

Consecutive test cases are separated by newlines.

输出格式

The minimum amount of moonies that Bessie needs to spend for each test case, on separate lines.

样例 1

样例输入 1

2

3 7 9
4 3 18
2 4 19
1 1 6

5 7 3
5 9 45
5 2 31
6 4 28
4 1 8
5 2 22

样例输出 1

11
6

提示

Explanation for Sample 1

$\qquad$In the first test case, Bessie can pay $11$ moonies to decrease the time required to produce a cookie by $4$ and a muffin by $7$, so that her oven produces cookies in $3$ units of time and muffins in $2$ units of time. Then she can satisfy the first friend in $18$ units of time, the second friend in $14$ units of time, and the third friend in $5$ units of time, so none of them will get sad and leave.

$\qquad$In the second test case, Bessie should decrease the time required to produce a cookie by $6$ and a muffin by $0$.

SCORING

• Inputs $2-4$: $N \le 10,t_C,t_M \le 1000$.
• Inputs $5-11$: No additional constraints.

题解

算法分析

题目简介：

有 $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$ 一定具有单调性，显而易见。于是问题变为了检验正确性。

怎么检验啊? 设 $\operatorname{mid}=x+y$ ，推下不等式呗。

$\qquad a \times\left(t_{c}-x\right)+b \times\left[t_{m}-(\operatorname{mid}-x)\right] \leq c_{\text {。 }}$

拆括号得： $a \times t_{c}-a \times x+b \times t_{m}-b \times \operatorname{mid}+b \times x \leq c_{。}$

下一步怎么搞？不妨试试：移项把 $a$ 和 $b$ 凑在一起。

$\qquad b\times x-a \times x \leq c-a \times t_{c}-b \times t_{m}+b \times mid$。

即：

$\qquad (b-a) \times x \leq c-a \times t_{c}-b \times t_{m}+b \times \operatorname{mid}_{。}$

为了方便，设：

$\qquad k=c-a \times t_{c}-b \times t_{m}+b \times m i d_{。}$

于是就能对 $a-b$ 的取值分米讨论啦。

• 若 $a-b>0$ : 原式不变， $x \leq \frac{k}{a-b}$ ，向下取值 ($floor$)。
• 若 $a-b=0$ : 若 $k<0$ ，则无解。
• 若 $a-b<0$ : 变号即可, $x \geq \frac{k}{a-b}$, 向上取值 ($ceil$)。

最终会得到一大堆与 $x$ 有关的大小关系式，判断是否有解即可。

关于上下界：设 $m i \leq x \leq m a$ 。

• 对于 $m i$ : 可以一个不减。但如果另一个数没法再减了，则必须要减它了，另一个数可以减去 $y-1$次, 因此取 $0$ 和 $m i d-t_{m}+1$ 的最大值。
• 对于 $m a$ : 至多把 $t_{c}$ 减到 $1$ ，不过 $m i d$ 得够大，因此取 $t_{c}-1$ 和 $m i d$ 的最小值。

代码

#include<bits/stdc++.h>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define int long long 
inline int input(){int x;return cin>>x,x;}
const int inf = 1e18+14;
const int N = 105;

int a[N],b[N],c[N];
int n,Tc,Tm,res;

int d[N],e[N];

inline bool check(int W){
	int L=max(0ll,W-Tm+1),R=min(W,Tc-1);
	For(i,1,n){
		int up=c[i]+b[i]*W-(a[i]*Tc+b[i]*Tm);
		if(b[i]-a[i]==0 && up<0) return false;
		if(b[i]-a[i]>0) R=min(R,(int)floor(1.0*up/(b[i]-a[i])));
		if(b[i]-a[i]<0) L=max(L,(int)ceil(1.0*up/(b[i]-a[i])));
	}return L<=R;
}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	freopen("a.in","r",stdin);
	freopen("a.out","w",stdout);
	int T=input();
	while(T--){
		cin>>n>>Tc>>Tm;
		For(i,1,n) cin>>a[i]>>b[i]>>c[i];
		int l=-1,r=Tc+Tm-1,mid;
		while(l+1<r){
			mid = (l+r)/2;
			if(check(mid)) r=mid;
			else l=mid;
		}cout<<r<<'\n';
	}
	return 0;
}