T
2025-10-19 14:55:28
发布于：浙江
3阅读
0回复
0点赞
T5-4
Bakery S 题解
题名：史迪仔的冰激凌店
题面：
史迪仔在经营一家冰激凌店，最近天气越来越热，他决定引入新产品冰沙。果然，来店里的顾客越来越多了，但是店里只有一台机器，每次只能生产一个冰激凌或一杯冰沙，并且生产一个冰激凌需要消耗 $t\_c$ 的时间，生产一杯冰沙需要 $t\_m$ 的时间，由于冰激凌和冰沙放一会就会化掉，所以史迪仔只会在顾客点单时才开始制作。每天店里会来 $n$ 个顾客，每个顾客会点 $A\_i$ 个冰激凌和 $B\_i$ 杯冰沙，而且每位顾客只愿意等待 $C\_i$ 的时间，超过这个时间顾客就会给差评然后离开。
史迪仔不想流失顾客，但是他的资金有限，买不起第二台机器，所以他决定去工厂升级一下现在的这台机器。工厂告诉史迪仔，$1$ 块钱可以让生产冰激凌或生产冰沙的时间减 $1$ （注意，是两者中的一个），但是时间不能小于等于 $0$，请你帮史迪仔算一下，最少需要花多少钱来升级设备才能不流失当天的顾客。
#### \*\*输入格式\*\*
共 $T$ 组数据，每组数据之间用换行隔开，对于每组数据：
第一行输入 $n,t\_c,t\_m$
接下来 $n$ 行各包含3个整数 $A\_i,B\_i,C\_i$
$1 \\leq T,n \\leq 100$
$1 \\leq t\_c,t\_m,A\_i,B\_i \\leq 10^9$
$A\_i+B\_i \\leq C\_i \\leq 2·10^{18}$
#### 输出格式
对于每组数据，输出需要花费的最少钱数，一行一个整数
#### 样例输入
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
#### 样例输出
11
6
#### 数据规模与约定
测试点 $1-3$：$n \\leq 10,t\_c,t\_m \\leq1000$
测试点 $4-10$：没有额外约束。
讲解时间：1小时
1、讲解题目+暴力写法：20分钟
2、为什么贪心不行+引入二分：5分钟
3、二分框架+单层枚举 15分钟
4、二分正解：20分钟
题目大意：
有一个机器，可以用 $t\_c$ 的时间生产一个冰激凌，用 $t\_m$ 的时间生产一杯冰沙，一次只能生产一种产品，会来 $n$ 个顾客，每个顾客想要点 $A\_i$ 个冰激凌和 $B\_i$ 杯冰沙，并且只愿意等待 $C\_i$ 的时间。
现在史迪仔可以花费1块钱来升级机器，让生产冰激凌或生产冰沙的时间减1，但时间必须大于0，注意是其中一种，共 $T$ 组输入，对于每组输入，求史迪仔最少花多少钱来升级机器可以满足所有顾客。
解题思路：
暴力写法：
假设史迪仔用 $x$ 块钱加速生产冰激凌，$y$ 块钱加速生产冰沙，那么 $x$ 和 $y$ 的取值应该分别为 $\[0,t\_c-1]$ 和 $\[0,t\_m-1]$，因为生产时间必须大于0，那么可以尝试使用两层 $for$ 循环枚举 $x$ 和 $y$ 的值，并写一个 $check()$ 函数判断当前的取值能否满足每个顾客的需求，如果能，记录下 $x+y$ 的值，答案就是所有可能值的最小值，如果不能，就继续枚举。
见参考代码，对了 $3$ 个测试点，$30$ 分。
看到题目要求的是最少花费，那我们进一步考虑使用贪心算法进行优化，看看能不能根据冰激凌和冰沙的需求总量来决定让谁的生产时间减少为 $1$，然后再只枚举另一个产品需要减少的时间。
例如下面这个样例：
1
2 5 5
10 1000 2050
100 10 550
显然对于这个样例，我们只需要让 $x=0,y=3$ 就可以满足所有顾客需求了，也就是最后的答案应该是 $3$，但按照贪心的想法，答案应该是 $4$。看起来贪心不像是正确解法，同学们也可以再想一想有没有别的贪心方案或者可不可以用另一种算法，我们求最小或最大的答案时，应该还有一种常用的算法。
题目要我们求一个最小的答案值，那我们是不是还学过一个算法叫做二分答案，它就是用来解决这种类型的题目的。根据题目描述，$mid$ 应该为史迪仔花费的钱数，但对于同一个 $mid$，史迪仔用于加速生产冰激凌的钱 $x$ 和用于加速生产冰沙的钱 $y$ 还是具有多种取值，我们还需要进行循环判断。不过由于已知 $x+y=mid$，所以我们只枚举 $x$ 的值就可以了，$y=mid-x$，那 $x$ 的取值范围应该是 $\[max(0,mid-(t\_m-1)),min(mid,tc-1)]$，因为当总钱数 $mid > t\_m-1$ 时，已经不能将钱花在加速生产冰沙上了，必须用在加速生产冰激凌上，同理，当 $mid > t\_c-1$ 时，必须把多余的钱用在加速生产冰沙上，现在让我们再试一下能不能够AC这道题。
见参考代码，还是只得到了 $30$ 分，那我们该怎么优化程序呢，是不是该考虑去掉 $for$ 循环呀。
让我们推导一下公式：
已知：
$$
\\begin{cases}
x+y=mid\\
A\_i\*(t\_c-x)+B\_i\*(t\_m-y) \\leq C\_i
\\end{cases}
$$
移项可得：
$$
A\_i\*t\_c-A\_i\*x+B\_i\*t\_m-B\_i\*(mid-x) \\leq C\_i\\
(B\_i-A\_i)\*x \\leq C\_i-A\_i\*t\_c-B\_i\*t\_m+B\_i\*mid
$$
为了方便理解，我们把右边的值设为 $K$，然后进行分类讨论。
当 $B\_i-A\_i=0$ 时，左值为 $0$，当 $K \\geq 0$ 时有无数解，当 $K<0$ 时无解。
当 $B\_i-A\_i>0$ 时，公式变为：$x \\leq K/(B\_i-A\_i)$，由于 $x$ 是整数，所以向下取整，这是 $x$ 的上界。
当 $B\_i-A\_i<0$ 时，公式需要变号：$x \\geq K/(B\_i-A\_i)$，同样由于 $x$ 是整数，向上取整，这是 $x$ 的下界。
为了方便理解，这里举两个例子：
$$
当\\ t\_c=7,t\_m=9,mid=11,A\_i=2,B\_i=4,C\_i=19\\ 时，K/(B\_i-A\_i)=6.5,B\_i-A\_i>0
$$
也就是 $x \\leq 6.5$，此时 $x$ 最大只能取 $6$，所以向下取整，并且是上界。
$$
当\\ t\_c=7,t\_m=3,mid=4,A\_i=4,B\_i=1,C\_i=8\\ 时，K/(B\_i-A\_i)=6.3333，B\_i-A\_i<0
$$
也就是 $x \\geq 6.3333$，此时 $x$ 最小只能取 $7$，所以向上取整，并且是下界。
由此，我们可以在 $check()$ 函数中遍历所有顾客，不断更新 $x$ 的上界和下界，只要最后 $x$ 的下界小于上界，也就是 $x$ 有解，就代表这个 $mid$ 是合法的，能够满足所有顾客需求，在这里我们不需要求出 $x$ 的具体值，只是用来判断 $mid$ 是否合法。
现在我们可以进行二分了，这里注意 $x$ 的上界 $maxn$ 和下界 $minn$ 的初始值应该分别为：
$$
maxn=min(t\_c-1,mid)\\
minn=max(0,mid-(t\_m-1))
$$
对于 $maxn$，由于生产时间不能小于等于 $0$，所以最大值为 $t\_c-1$，但如果 $mid<t\_c-1$，$x$ 最大只能取到 $mid$，所以取两者最小值；对于 $minn$，$x$ 可以取 $0$，表示不加速生产冰激凌，但如果 $mid>t\_m-1$，也就是把生产冰沙的时间减少到 $1$ 后，钱还有剩余，就必须用来加速生产冰激凌，所以取两者的最大值。
在二分前注意通过 $check(0)$ 判断不花钱的情况，参考样例：
样例输入：
1
1 1 1
1 1 5
样例输出：
0
参考代码：
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
const int MAXN=105;
int T,n;
ll tc,tm;
ll a\[MAXN],b\[MAXN],c\[MAXN];//如题目描述
bool check(int x,int y){//判断是否超过等待时间
for(int i=1;i<=n;i++){
if(a\[i]\*(tc-x)+b\[i]\*(tm-y)>c\[i]) return 0;//超过就返回0
}
return 1;//没超过返回1
}
int main(){
cin>>T;
while(T--){//T组数据
cin>>n>>tc>>tm;
for(int i=1;i<=n;i++){
cin>>a\[i]>>b\[i]>>c\[i];
}
ll minn=tc+tm;
for(ll i=0;i<tc;i++){//x,0~tc-1
for(ll j=0;j<tm;j++){//y,0~tm-1
if(check(i,j)){//判断是否合法
minn=min(minn,i+j);//取最小值
}
}
}
cout<<minn<<endl;
}
return 0;
}
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long int ll;
const int MAXN=105;
int T,n;
ll tc,tm;
ll a\[MAXN],b\[MAXN],c\[MAXN];//如题目描述
bool check(int x,int y){//判断是否超过等待时间
for(int i=1;i<=n;i++){
if(a\[i]\*(tc-x)+b\[i]\*(tm-y)>c\[i]) return 0;//超过就返回0
}
return 1;//没超过返回1
}
int main(){
cin>>T;
while(T--){//T组数据
cin>>n>>tc>>tm;
for(int i=1;i<=n;i++){
cin>>a\[i]>>b\[i]>>c\[i];
}
if(check(0,0)){//特判一下不花钱的情况
cout<<0<<endl;
continue;
}
ll l=1,r=tc+tm-2;
ll ans=-1;//答案
while(l<=r){//二分框架
ll mid=(l+r)>>1;
bool flag=0; //是否存在合法的情况
for(int i=max(0ll,mid-(tm-1));i<=min(mid,tc-1);i++){//x的取值范围
if(check(i,mid-i)){//如果存在合法情况
flag=1;//标记并退出循环
break;
}
}
if(flag){
ans=mid;//更新答案
r=mid-1;
}
else{
l=mid+1;
}
}
cout<<ans<<endl;
}
return 0;
}
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long int ll;
const int MAXN=105;
int n,T;
ll tc,tm;
ll a\[MAXN],b\[MAXN],c\[MAXN];
bool check(ll mid){
ll maxn=min(tc-1,mid),minn=max(0ll,mid-tm+1);//设置初值
for(int i=1;i<=n;i++){
ll k=c\[i]-a\[i]\*tc-b\[i]\*tm+b\[i]\*mid;//k值
if(b\[i]-a\[i]==0\&\&k<0) return 0;//分类讨论
else if(b\[i]-a\[i]>0) maxn=min(maxn,(ll)floor((double)k/(b\[i]-a\[i])));//注意更新时需要和原值比较
else if(b\[i]-a\[i]<0) minn=max(minn,(ll)ceil((double)k/(b\[i]-a\[i])));
}
return minn<=maxn;//判断是否有解
}
int main(){
cin>>T;
while(T--){//T组输入
ll ans=-1;//答案
cin>>n>>tc>>tm;
for(int i=1;i<=n;i++){
cin>>a\[i]>>b\[i]>>c\[i];
}
if(check(0)){//判断不花钱的情况
cout<<0;
continue;
}
ll l=1,r=tc+tm-2;//二分答案框架
while(l<=r){
ll mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}
else{
l=mid+1;
}
}
cout<<ans<<endl;
}
return 0;
}
这里空空如也
有帮助，赞一个