返回

P4480 [BJWC2018] 餐巾计划问题

一道贪心,四倍经验一黑三紫

前言

很久之前就把自己博客题解分区这个功能做出来了,但是一直没有去写题解。正好昨晚刚做出来一道比较简单的黑题,还热乎着,所以就写一写吧。

其实这是我的第二道黑题,也是第一道三分题,所以成为我的第一道题解还是很可以接受的。

不要害怕紫题黑题,实际上有可能只是思维难度高,实现起来比普及题还容易。而且如果你真的想在 OI 这条路上走远一点,迟早会做紫黑的。

题意

题目描述很清楚,因此直接复制洛谷上的了:

一个餐厅在相继的 $n$ 天里,每天需用的餐巾数不尽相同。假设第 $i$ 天 $(i=1,2,…,n)$ 需要 $r_i $​ 块餐巾。餐厅可以在任意时刻购买新的餐巾,每块餐巾的费用为 $p$ 。使用过的旧餐巾,则需要经过清洗才能重新使用。把一块旧餐巾送到清洗店A,需要等待 $m_1$​ 天后才能拿到新餐巾,其费用为 $c_1$​ ;把一块旧餐巾送到清洗店B,需要等待 $m_2​$ 天后才能拿到新餐巾,其费用为 $c_2$​ 。例如,将一块第 $k$ 天使用过的餐巾送到清洗店A清洗,则可以在第 $k+m_1$​ 天使用。

请为餐厅合理地安排好 $n$ 天中餐巾使用计划,使总的花费最小。

思路

其实这题原题是网络流,把天拆成早晚两个点然后进行连边,但是其实有更简单的贪心做法,并且在 $n$ 比较大的时候网络流还会被卡,所以这里只讲贪心。、

这里我们先假设 $m_1 \lt m_2$ 且 $c_1 \gt c_2$ ,即清洗店A快但贵,清洗店B慢但便宜,否则两者交换即可。我们形象地称呼前者为快洗,后者为慢洗。当然,这里还有一种特殊情况,就是慢洗比快洗贵,此时直接让 $m_2$ 等于 $m_1$ ,$c_2$ 等于 $c_1$,也就是相当于把慢洗换成快洗,这样就满足条件了。

首先一个注意到一个很显然的事实是,假设 $r_{1\to x}=r_1+r_2+\cdots+r_x$,即前缀和,那么我们需要购买的餐巾的数量的范围是 $[r_{1\to m_1},r_{1\to n}]$ 。因为就算是第一天开始快洗,我们也要到第 $m_1+1$ 天才能用,因此前面 $m_1$ 天需要的餐巾一定是靠买的;而当购买餐巾的费用比去慢洗还便宜的时候,自然是只买不洗的花费最小,此时 $n$ 天的餐巾全靠买。

尽管餐厅随时可以购买餐巾,但全部在最开始就买好一定是更优的,并且买来的越早用越好,因为提前买好提前用的话可能还可以靠洗来少买几条,或者换句话说就是餐巾利用率比较高。

这里我们转变一下视角,不是提前去洗好,而是换成当你餐巾不够用时,再从过去调度几块过来。(这应该算是一个比较常用的trick)

这样当我们已经决定好最开始买多少条餐巾时,可以发现后面 $n$ 天的贪心就很显然了:先用已经买好的,其次尽可能选择慢洗,最后再选择快洗。并且快洗尽可能选择较晚的餐巾,因为这样我们把较早的餐巾保留下来,过几天之后就可以用于慢洗。

这样看来,我们假设最开始买 $x$ 条餐巾,在确定的贪心方案下,最后的总费用应该也是确定并且与 $x$ 一一对应的,我们假设其为 $f(x)$ 。而我们一开始说过 $x$ 有范围,那么我们枚举 $x$ ,这题的答案应该就是 $\max f(x)$ 了。

本题到此,已经算是做出来了,接下来就是很经典的trick:范围内枚举,单次枚举不是 $O(1)$ ,这时候单调函数求零点就用二分,单峰函数求最值可以三分或者斜率二分,多峰函数求最值可以爬山或者模拟退火。

我们合理推测,如果一开始餐巾买少了,后面要么不够用,要么就得多洗几次快洗来弥补;如果一开始餐巾买多了,可以靠慢洗省下的费用都没省到。因此本题外层是一个单峰求最小值,我们进行一个三分或者斜率二分即可,本题结束。

代码

上面貌似讲了很多,但其实代码一点都不复杂,而且听起来时间复杂度很高,但实际上跑的飞快。check() 的时间复杂度是 $O(n(m_2-m_1))$ ,三分的时间复杂说法很多,所以这里就不算总复杂度了,能过,而且跑的飞快。

代码的部分有个小优化,做的时候很自然的想到的,就是对于所有能慢洗的餐巾,无论什么时候用的,哪怕你是远古时期用过的餐巾,都是等价的,所以我使用了一个变量 $f$ 直接来存可以慢洗的毛巾,这样就不需要枚举了,这也是为什么我比参考文献中那篇题解快,以及四倍经验里面拿到了三题的最优解。

另外这题看数据范围是需要开 long long 的,但实测不需要,估计是数据太水了。但尽管我觉得数据水,这个数据还是会卡掉大部分写的不好的网络流做法。

#include<cstdio>
#include<algorithm>
#define N 200005
#define INF 0x3f3f3f3f
using namespace std;

int n, m1, m2, c1, c2, p, r[N], res[N];
//res[i] 表示第 i 天使用过的毛巾的数量

inline int check(int num) {
    int ans=num*p, f=0; //先买餐巾
    for(register int i=1; i<=n; ++i) {
        res[i] = 0; //使用前先清空
        if(i > m2)    f += res[i-m2]; //统计可以慢洗的餐巾
        int need=r[i], k=min(need, num); //先用买好的
        need-=k, num-=k, res[i]+=k;
        if(!need)    continue;
        k = min(need, f); //慢洗
        need-=k, f-=k, res[i]+=k, ans+=k*c2;
        if(!need)    continue;
        for(register int j=i-m1; j&&j>i-m2; --j) { //快洗,越晚越好
            k = min(need, res[j]);
            need-=k, res[j]-=k, res[i]+=k, ans+=k*c1;
            if(!need)    break;
        }
        if(need)    return INF; //餐巾不够用,刚开始买少了,直接返回INF即可
    }
    return ans;
}

int main() {
    scanf("%d%d%d%d%d%d", &n, &m1, &m2, &c1, &c2, &p);
    if(m1 > m2)    swap(m1, m2), swap(c1, c2); //确保1为快洗,2为慢洗
    if(c1 < c2)    m2=m1, c2=c1;
    int l=0, rr=0;
    for(register int i=1; i<=n; ++i)    scanf("%d", &r[i]), rr+=r[i];
    for(register int i=1; i<=m1; ++i)    l += r[i]; //l和rr是三分的范围
    int ans = INF;
    while(rr-l > 2) { //很普通的三分
        int mid1=(l*2+rr)/3, mid2=(l+rr*2)/3;
        int f1=check(mid1), f2=check(mid2);
        if(f1 < f2)    ans=min(ans, f1), rr=mid2-1;
        else    ans=min(ans, f2), l=mid1+1;
    }
    for(register int i=l; i<=rr; ++i)    ans = min(ans, check(i));
    printf("%d", ans);
    return 0;
}

附录

原题链接

四倍经验,一道黑三道紫,数据范围还都比本题小很多,经验什么时候这么好赚了?而且除了 P1251 外剩下三题我都是最优解。

参考文献

  1. P4480 「BJWC2018」「网络流与线性规划24题」餐巾计划问题 - HenryHuang 的博客 - 洛谷博客

版权信息

本文原载于reincarnatey.net,遵循CC BY-NC-SA 4.0协议,复制请保留原文出处。

CC BY-NC-SA 4.0
本博客所有内容无特殊标注均为失迹原创内容,复制请保留原文出处。
Built with Hugo
Theme Stack designed by Jimmy, mod by Korita
© Licensed Under CC BY-NC-SA 4.0