P9124 [USACO23FEB] Bakery S 题解

MiPloRAs_3316 · 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;
}