洛谷P4694 [PA2013] Raper 题解

题目链接：P4694 [PA2013] Raper

题意：

你需要生产 $k$ 张光盘。每张光盘都要经过两道工序：先在 A 工厂进行挤压，再送到 B 工厂涂上反光层。

你知道每天 A、B 工厂分别加工一张光盘的花费。你现在有 $n$ 天时间，每天可以先送一张光盘到 A 工厂（或者不送），然后再送一张已经在 A 工厂加工过的光盘到 B 工厂（或者不送），每家工厂一天只能对一张光盘进行操作，同一张光盘在一天内生产出来是允许的。我们假定将未加工的或半成品的光盘保存起来不需要费用。

求生产出 $k$ 张光盘的最小花费。

输入格式

第一行包含两个整数 $n, k$，表示有 $n$ 天，要生产 $k$ 张光盘。

第二行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 天送到 A 工厂加工光盘的花费。

第三行包含 $n$ 个整数，第 $i$ 个整数表示第 $i$ 天送到 B 工厂加工光盘的花费。

输出格式

输出一行一个整数，表示最小花费。

数据范围：

保证 $1 \le k \le n \le 5 \times 10^5,~1 \le a_i, b_i \le 10^9$。

首先本题有一个显然的费用流做法：

$S$ 向 $i$ 连边，费用为 $a_i$ ，流量为 $1$ 。 $(1 \le i \le n)$
$i$ 向 $T’$ 连边，费用为 $b_i$ ，流量为 $1$ 。$(1 \le i \le n)$
$i$ 向 $i+1$ 连边，费用为 $0$ ，流量为 $+\infty$ 。$(1 \le i < n)$
$T’$ 向 $T$ 连边，费用为 $0$ ，流量为 $k$ 。

那么从 $S$ 向 $T$ 跑最小费用最大流，得到的费用就是答案，时间复杂度为 $\mathcal{O}(nmk)$

这个做法显然跑不过，接着就有两种选择：模拟费用流 / wqs 二分。

因为我不会模拟费用流，所以我就来讲讲 wqs 二分的解法吧。（模拟费用流的解法可以看下面的参考文献3）

结论如果是一个费用流模型，那么它一定具有下凸性。

证明因为在最小费用最大流的过程中，会优先增广最短路

所以增广完最短路之后不会增广更短的路，那么可知原函数满足下凸性。 $\square$

~~当然你也可以打表找规律~~。

于是现在我们就不需要考虑 $k$ 的限制了，现在考虑怎么获得最小的花费。

考虑用一个小根堆维护当前的决策。如果当前 $b_i$ 的花费加上决策花费后为非正数，那么优先选择该决策。

又因为 $a_i + b_j - b_j + b_k = a_i + b_k$ ，我们每次决策后将 $-b_i$ 放到堆里，这样下次取出它就相当于反悔了。

注意 wqs 二分时应该尽可能多选择物品。否则对于斜率相同的情况会无法处理。

那么当正常选的决策和反悔的决策花费相同时，我们优先选择正常选的决策，这样可以拿更多的物品。

时间复杂度 $\mathcal{O}(n \log n\log V)$ ，比模拟费用流慢（不过 wqs 二分和反悔贪心还是蛮常见的吧）。

代码：（注意不要写反向优化，比如 static 的优先队列。）

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
typedef long long ll;
void up(int &x, int y) { x < y ? x = y : 0; }
void down(int &x, int y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)(5e5 + 15))

int n, m, a[N], b[N]; ll sum, now;
struct node { ll w; bool pd; };
bool operator<(const node&x, const node&y) { 
    return x.w == y.w ? x.pd < y.pd : x.w > y.w;
}
bool check(ll x)
{
    sum = now = 0; priority_queue<node> q;
    rep(i, 1, n)
    {
        q.push({a[i] - x, 1}); node u = q.top();
        if(u.w + b[i] <= 0)
        {
            sum += u.w + b[i]; now += u.pd;
            q.pop(); q.push({-b[i], 0});
        }
    }
    return now >= m;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    rep(i, 1, n) cin >> a[i];
    rep(i, 1, n) cin >> b[i];
    ll l = 0, r = 2e9;
    while(l < r)
    {
        int mid = (l + r) >> 1;
        check(mid) ? r = mid : l = mid + 1;
    }
    check(l); cout << sum + l * m << '\n';
    return 0;
}