题目描述

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

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

求生产出 kk 张光盘的最小花费。1kn5×105,1 \leqslant k \leqslant n \leqslant 5 \times 10^5, 1ai,bi1091 \leqslant a_i, b_i \leqslant 10^9

思路

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

  • SS 向每一个 A 工厂连接一条容量为 11,费用为 aia_i
  • 每一个 A 工厂向 SS 连接一条容量为 11,费用为 bib_i
  • 对于第 ii 个 A 工厂,向所有的 jij \ge i 的 B 工厂连一条容量为 11,费用为 00 的边。

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

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

  • 如果 bib_i 和之前的任何一个 aia_i 都会使花费增加,则不匹配。
  • 和之前没匹配的 aia_i 匹配。
  • 拆开前面的一组进行匹配。

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

总时间复杂度 O(nlog2n)\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;
}