洛谷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)
结论 如果是一个费用流模型,那么它一定具有下凸性。
证明 因为在最小费用最大流的过程中,会优先增广最短路
当然你也可以打表找规律。
于是现在我们就不需要考虑 \(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;
}
本题是三倍经验:
参考文献:
[1] https://www.luogu.com.cn/article/6ryjfu26
[2] https://www.luogu.com.cn/article/ko2plqh0
[3] https://www.luogu.com.cn/article/wes66yc7
题外话:
放图片。