P4694「PA2013」 Raper

题目描述

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

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

求生产出 $k$ 张光盘的最小花费。 $1 \leqslant k \leqslant n \leqslant 5 \times 10^5,$ $1 \leqslant a_i, b_i \leqslant 10^9$ 。

思路

题目很像一个匹配问题，首先考虑费用流。有一个显然的建图方式。

$S$ 向每一个 A 工厂连接一条容量为 $1$ ，费用为 $a_i$ 。
每一个 A 工厂向 $S$ 连接一条容量为 $1$ ，费用为 $b_i$ 。
对于第 $i$ 个 A 工厂，向所有的 $j \ge i$ 的 B 工厂连一条容量为 $1$ ，费用为 $0$ 的边。

考虑限制源点的流量，对于找增广路的过程费用是下凸的。所以我们考虑 wqs 二分。现在我们已经二分一个斜率，每次匹配都需要减去这个斜率。下文假设这个斜率是 $x$ 。

如何判断。匹配可以分为三种：

如果 $b_i$ 和之前的任何一个 $a_i$ 都会使花费增加，则不匹配。
和之前没匹配的 $a_i$ 匹配。
拆开前面的一组进行匹配。

这是个反悔贪心的过程。使用堆维护即可。具体的，在完成一对匹配后弹出 $a_i$ 插入 $x - b_i$ ，这样反悔的时候可以消除之前的 $b$ 的影响。

总时间复杂度 $\mathcal{O}(n \log^2 n)$ 。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
using ll = long long;

ll n, k, a[N], b[N];
ll Ans;

ll check(ll mid) {
    Ans = 0; int cnt = 0;
    priority_queue<pair<ll, bool>, vector<pair<ll, bool> >, greater<pair<ll, bool> > > q;
    for (int i = 1; i <= n; i++) {
        q.emplace(a[i], true);
        pair<ll, bool> x = q.top();
        if (x.first + b[i] - mid > 0) continue; 
        q.pop();
        Ans += x.first + b[i] - mid;
        cnt += (x.second == true);
        q.emplace(mid - b[i], false);
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    ll l  =0, r = 1e15, mid, res;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid) < k) res = mid, l = mid + 1;
        else r = mid - 1;
    }
    check(mid);
    cout << Ans + mid * k << endl;
    return 0;
}