题解：AT_abc374_e [ABC374E] Sensor Optimization Dilemma 2

· · 题解

ABC374E

题目大意

生产某种产品需要 N 个编号为 1,2,\dots,N 的工序 。

每道工序 i 都有两种机器 S_i 和 T_i 可供购买使用 。

您可以购买任意数量的每台机器，有可能是零 。

假设引入机器后，工序 i 每天可以处理 W_i 个产品。

在此，我们将生产能力定义为 W 的最小值，即 \displaystyle \min^{N}_{i=1} W_i 。

在总预算为 X 日元的情况下，求可实现的最大生产能力 。

思路

这道题目看到 “ 最小值最大 ” 这个词 ， 就可以想到这道题是二分答案 。

而二分的东西也很简单 ， 就是我们的生产能力（即要输出的答案） 。

关键是怎么判断达到生产能力所需的价值是否合法 ( 也就是 check 怎么写 ) 。

大体做法是这样 ：

首先 ， 对于每一个流程 ， 我们可以去枚举选多少个 S 机器,

然后 ，我们可以分别计算出购买 S 机器的花费和购买 T 机器的花费，就可以计算出流程 W 的花费 。

然后我们把计算出来的总价值与 X（ 同题目描述 ） 比较即可 。

具体的 ：

假设每天要处理 mid 件产品 ，

然后 ， 我们买了 j 个 S 机器 ， 则每天可以处理 j \times a_i 个产品 ， 花费是 j \times p_i 日元 。

这个时候 ， 我们还需要用 T 机器来补齐剩下要处理的 mid-j \times a_i 个产品， 需要买 \lceil{\frac {mid-j \times a_i} {b_i}}\rceil 件 ， 花费是 \lceil{\frac {mid-j \times a_i} {b_i}}\rceil \times q_i 日元 。

则买 j 个 S 机器的总花费为 j \times p_i + \lceil{\frac {mid-j \times a_i} {b_i}}\rceil \times q_i 。

这个流程的最小花费就是买 1 到 X \div p_i 件 S 机器中花费最小的情况 。

接着我们算出所有流程的最小花费并统计它们的和 ，

Code1：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 110;
int a[maxn],b[maxn];
long long p[maxn],q[maxn];
int n,m;
//n,a[],p[],b[],q[]都和题目描述一样
//m是目前拥有的总价值，也就是题目描述中的 X
bool check(int x){
    int cm = m;
    for(int i = 1;i <= n;i++){
        long long nans = 2e7;
        for(int j = 0;j <= m / p[i];j++)
            if(j * a[i] >= x){
                nans = min(nans,j * p[i]);
                break;
            }
            else nans = min(nans,j * p[i] + (x - j * a[i] + b[i] - 1) / b[i] * q[i]);
        cm -= nans; 
        if(cm < 0)return 0;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> n >> m;
    for(int i = 1;i <= n;i++)
        cin >> a[i] >> p[i] >> b[i] >> q[i];
    int l = 0,r = 1000000001;
    while(r - l > 1){
        int mid = (l + r) >> 1;
        if(check(mid))l = mid;
        else r = mid;
    }
    cout << l;
}

复杂度是二分的 O( \log 10^9)，和内层循环的 O(n^2) 。

总时间复杂度是 O(n^2 \log 10^9) ，也就是 O(n^2) 。

而此题的 n 又只有 100 。

所以 ， 这种方法是可以通过此题的 。

但是，这还不够好

我们发现，随着选择 T 机器的个数变多 ， 花费和生产力的关系是这样变化的 。

即先递减后递增（或先递增后递减）。

这是一个单谷函数 。

而与单谷函数相关的算法就是三分 。

于是我们考虑用二分套三分来实现此题 。

不会这一部分的请先移步P1883 【模板】三分 | 函数 。

三分具体实现方法 ：

我们每次选出两个点 mid1 和 mid2 。

其中 mid1 为左三等分点 ， mid2 为右三等分点 。

比较选 mid1 件 S 机器的花费和选 mid2 件 S 机器的花费 ，

做完三分后 ， 我们就和原先一样处理每个流程花费的总合 ，并与 X 比较大小即可 。

因为三分的复杂度是 O(2 \log_3 n) 的 ,

这样 ， 我们就可以把原先的 O(n^2) 变成 O(2n \log_3 n) ，

即 O(n \log n) 。

经实测 ， 上面的办法速度是原先办法的 50 倍以上 。

\xcancel{但似乎不是最优解}

Code2:


#include<bits/stdc++.h>
using namespace std;
long long n,m,l,r,mid,ans,a[105],p[105],b[105],q[105];
bool f(long long x)
{
    long long sum=0;
    for(long long i=1;i<=n;i++)//枚举每一个流程
    {
        long long l=0,r=x*1.0/a[i]+1,mid1,mid2,mid,ans=0;
        while(l<=r)//三分
        {
            mid1=l+(r-l)/3;
            mid2=r-(r-l)/3;
            long long s1=(x-mid1*a[i])/b[i],s2=(x-mid2*a[i])/b[i];
            if((x-mid1*a[i])%b[i]!=0)
                s1++;
            if((x-mid2*a[i])%b[i]!=0)
                s2++;
            long long ans1=mid1*p[i]+s1*q[i],ans2=mid2*p[i]+s2*q[i];//计算mid1和mid2的花费
            if(ans1<ans2)r=mid2-1,ans=mid2;
            else l=mid1+1,ans=mid1;
        }
        long long ans2=ans,w=0,minn=2e15;
        long long s2=x/a[i]*p[i];
        if(x%a[i]!=0)
            s2+=p[i];
        if(s2<minn)
        {
            minn=s2;
            w=x/a[i];
            if(x%a[i]!=0)
                w++;
        }
        for(long long ans=max(0ll,ans2-1000);ans<=min(x/a[i],ans2+1000);ans++)//统计花费总和
        {
            long long num1=(x-ans*a[i])/b[i];
            if((x-ans*a[i])%b[i])
                num1++;
            long long sum1=ans*p[i]+num1*q[i];
            if(sum1<minn)
                minn=sum1,w=ans;
        }
        sum+=minn;
        if(sum>m)
            return 0;
    }
    return sum<=m;
}
signed main()
{
    scanf("%lld%lld",&n,&m);
    for(long long i=1;i<=n;i++)
        scanf("%lld%lld%lld%lld",&a[i],&p[i],&b[i],&q[i]);
    l=0,r=100000000000;
    while(l<=r)//二分
    {
        mid=(l+r)/2;
        if(f(mid))
        {
            l=mid+1;
            ans=mid;
        }
        else
            r=mid-1;
    }
    printf("%lld",ans);
    return 0;
}