LuoGu: CF802O April Fools’ Problem (hard)
CF: O. April Fools’ Problem (hard)
答案是关于 $k$ 的凸函数，随着 $k$ 增大，答案一定增大，增大的速度越来越快。因此可以用 wqs二分 。
现在考虑每个匹配都减少一个权值，没有了 $k$ 的限制。可以用二维 DP 完成，时间复杂度为 $O(n ^ 2 \log n)$ ，不能通过此题。
考虑带悔贪心。每次将 $a _ i$ 放入堆中，每个后面的 $b _ i$ 可以匹配到前面的 $a _ i$ 。考虑反悔，如果 $b _ j < b _ i$ ， $b _ j$ 可以替换 $b _ i$ 。因此，每次匹配后，将 $b _ i$ 放入堆中。
细节：
- 本题中，斜率不是严格单调的，因此一个斜率意味着多个答案。在贪心中，相等的答案尽量不取，答案就可以所有该斜率中的最小值。找到一个 $mid$ 使得 $cnt \le m$ ，而 $mid + 1$ 则 $cnt > m$ ，那么 $k$ 在斜率 $mid$ 上，可以确定答案。
- 注意一个匹配，减少一个权值，二分的范围为一个匹配的值域。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <cstdio>
#include <queue>
using namespace std;
typedef long long LL;
typedef pair<LL, int> PLI;
const int N = 5e5 + 10;
LL ans;
int n, m, cnt, A[N], B[N];
void check(LL x)
{
cnt = ans = 0;
priority_queue<PLI, vector<PLI>, greater<PLI>> q;
for (int i = 1; i <= n; i++)
{
q.push(make_pair(A[i] - x, 1));
PLI t = q.top();
if (B[i] + t.first >= 0)
continue;
q.pop();
cnt += t.second;
ans += B[i] + t.first;
q.push(make_pair(-B[i], 0));
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &A[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &B[i]);
LL l = 0, r = 2e9, res;
while (l <= r)
{
LL mid = l + r >> 1;
check(mid);
cnt <= m ? (res = ans + (LL)mid * m, l = mid + 1) : r = mid - 1;
}
printf("%lld", res);
return 0;
}
|
用模拟费用流也可以理解此题，见 P4694 。