题解 P4480 【[BJWC2018]餐巾计划问题】

· · 题解

题解-[BJWC2018]餐巾计划问题

好好的网络流题，变成了队列加模拟。

参考资料

暂无

博客中原文

\color{#000}\texttt{Introduction}

蒟蒻在刷省选水题时发现一道 [HNOI2001]软件开发，与当年的网络流题 餐巾计划问题 一模一样。然后蒟蒻又看了讨论，这两题又和 [USACO08NOV]Toys G 和 [BJWC2018]餐巾计划问题 除了数据范围以外一模一样。然后这题就是其中数据范围最强的了，做法竟然是队列和模拟。

\color{#000}\texttt{Description}

[BJWC2018]餐巾计划问题

有 n 天，每天需要 r_i 块干净餐巾给人用，用完后会脏。每天买新干净餐巾 p 元每块，洗脏餐巾需要 c_1 元每块耗时 m_1 天或 c_2 元每块耗时 m_2 天。求最少花费。

数据范围：1\le n\le 2\times 10^5，1 \le m_1, m_2 \le n，1 \le c_1, c_2, p \le 100，1 \le r_i \le 100 。

\color{#000}\texttt{Solution}

网络流的 50\sim90 分做法就不赘述了。

首先从两种洗餐巾方式入手。把 m 大的洗餐巾方式叫慢洗，反之叫快洗。如果慢洗比快洗贵，把慢洗设为和快洗一模一样。这样我们就有快洗快而贵，慢洗慢而便宜两种洗法了。令快洗时间为 t_k，价格为 f_k 每块；慢洗时间为 t_m，价格为 f_m 每块（t_k\le t_m,f_k\ge f_m）。

买的餐巾总数 x 是不定的，如果买多了也耗钱，买少了洗得多也耗钱。所以可以直觉推断买餐巾数量一定的情况下最少耗钱随 x 而变化的图像是 V 字型，所以可以三分或斜率二分，找到这个 x。

但是知道了 x，怎么计算最优耗钱呢？首先要早买餐巾，因为早点买早点用早点洗对每个餐巾的利用率高。所以可以用买餐巾解决前几天的需求。

然后是能用慢洗不用快洗，很明显，因为快洗贵。

所以可以用三个双向队列维护脏餐巾（每天用完的餐巾）、慢洗完的餐巾（用完后至少 t_m 天）、快洗完的餐巾（用完后 t_k\sim t_m-1）。每天把脏餐巾队列的末尾用完时间到 t_k 天的餐巾放进快洗完的餐巾队列头，然后把快洗完的餐巾队列末尾时间到 t_m 的餐巾放进慢洗完的队列头。然后按先买再慢洗最后快洗的顺序模拟即可。

特别的，如果某天的要求怎么都满足不了，就返回 \infty。

最后答案就是三分或斜率二分得到的耗钱谷点的耗钱数。

\color{#000}\texttt{Code}

#include <bits/stdc++.h>
using namespace std;

//&Start
#define lng long long
#define lit long double
const int inf=0x3f3f3f3f;
const lng Inf=1e17;

//&Check
const int N=2e5+10;
int n,r[N],fx,fm,fk,Tm,Tk,sm,ans=inf;
struct bag{int T,v;};
//买来的时间、数量（把多份一起买的餐巾打包）
deque<bag> qx,qm,qk;//新买、慢洗、快洗
int f(int x){//买x块餐巾计算最优耗钱
    int res=x*fx;//买餐巾的钱
    qx.clear(),qm.clear(),qk.clear();
    for(int i=1;i<=n;i++){
        while(qx.size()&&qx.front().T+Tk<=i)
            qk.push_back(qx.front()),qx.pop_front();
        //把旧餐巾快洗完的丢进快洗队列
        while(qk.size()&&qk.front().T+Tm<=i)
            qm.push_back(qk.front()),qk.pop_front();
        //把快洗完的餐巾慢洗完的丢进慢洗队列
        int nd=r[i],by=min(nd,x);//如果还可以买餐巾就先买
        x-=by,nd-=by;
        while(nd&&qm.size()){//先慢洗
            by=min(nd,qm.back().v);
            nd-=by,res+=by*fm;
            if(by==qm.back().v) qm.pop_back();//用完了
            else qm.back().v-=by;
        }
        while(nd&&qk.size()){//再快洗
            by=min(nd,qk.back().v);
            nd-=by,res+=by*fk;
            if(by==qk.back().v) qk.pop_back();//用完了
            else qk.back().v-=by;
        }
        if(nd) return inf;
        qx.push_back((bag){i,r[i]});
    }
    return res;
}

//&Main
int main(){
    scanf("%d%d%d%d%d%d",&n,&Tm,&Tk,&fm,&fk,&fx);
    if(Tm<Tk) swap(Tm,Tk),swap(fm,fk);
    if(fm>fk) Tm=Tk,fm=fk;//保证快洗快贵，慢洗慢便宜
    for(int i=1;i<=n;i++) scanf("%d",r+i),sm+=r[i];
    int l=0,r=sm+1;
    while(l<r-1){//斜率二分
        int mid=(l+r)>>1;
        if(f(mid)<f(mid+1)) r=mid;
        else l=mid;
    }
    printf("%d\n",f(r));//Go!
    return 0;
}

然后把这份代码交到另外三题，就妥妥四倍经验了。我还是太蒻了。祝大家学习愉快！