USACO23FEB-Silver A

题目来源

洛谷： USACO23FEB-Silver Milk Sum(A)

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

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

题目

题目描述（中文）

Bessie 开了一家面包店!

在她的面包店里，Bessie 有一个烤箱，可以在的时间内生产一块饼干或在单位时间内生产一块松糕。
。由于空间限制，Bessie 一次只能生产一种糕点，所以要生产块饼干和块松饼，需要单位的时间。

Bessie的朋友都想一个一个地去面包店。第个朋友一进门就会点块饼干和块松饼。Bessie 没有空间来储存糕点，所以她只有在接到订单后才开始制作糕点。此外，Bessie 的朋友都很忙，所以第个朋友只愿意等个单位的时间，然后就伤心地离开。

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

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

输入格式

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

每个测试用例都以一行开始，包含,,。然后，接下来的行各包含三个整数。

测试案例用换行符隔开。

输出格式

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

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

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

数据规模与约定

• 输入：。
• 输入，没有额外的约束。

题目描述(English)

Bessie has opened a bakery!

In her bakery, Bessie has an oven that can produce a cookie in
units of time or a muffin in
units of time. Due to space constraints, Bessie can only produce one pastry at a time, so to producecookies andmuffins, it takesunits of time.

Bessie’sfriends would each like to visit the bakery one by one. The-th friend will ordercookies andmuffins 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-th friend is only willing to waitunits of time before getting sad and leaving.

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.

For each oftest 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, the number of test cases.

Each test case starts with one line containing
,,. Then, the nextlines each contain three integers.

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

In the first test case, Bessie can paymoonies to decrease the time required to produce a cookie byand a muffin by, so that her oven produces cookies inunits of time and muffins inunits of time. Then she can satisfy the first friend inunits of time, the second friend inunits of time, and the third friend inunits of time, so none of them will get sad and leave.

In the second test case, Bessie should decrease the time required to produce a cookie byand a muffin by.

SCORING

• Inputs:.
• Inputs: No additional constraints.

题解

算法分析

题目简介：

有个人来买两种东西，要使，你可用一块钱减少或一个单位时间，但不能减到零。求最少要花费多少钱，才能使上式成立。

分析：

假设操作后，减去，减去，答案就是。

很容易想到二分，那么二分什么呢?

二分(或) 吗? 不对，不具有单调性，因为还可以调整。可能把调大点，调小点，说不定更优？

但一定具有单调性，显而易见。于是问题变为了检验正确性。

怎么检验啊? 设，推下不等式呗。

拆括号得：

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

。

即：

为了方便，设：

于是就能对的取值分米讨论啦。

• 若: 原式不变，，向下取值 ()。
• 若: 若，则无解。
• 若: 变号即可,, 向上取值 ()。

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

关于上下界：设。

• 对于: 可以一个不减。但如果另一个数没法再减了，则必须要减它了，另一个数可以减去次, 因此取和的最大值。
• 对于: 至多把减到，不过得够大，因此取和的最小值。

代码

#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;
}