【笔记】kth - 浅谈前 k 优解问题
第一次见到这一类的 trick 是在 SDOI2013 - 淘金，现在才知道这个 trick 还有一堆扩展。
Part 0.
这类问题的一个通用思路：
对于目前考虑到的一个状态 \(S\)，设 \(\operatorname{trans}(S)\) 为 \(S\) 的后继状态集合。
首先将最优的状态 \(S\) 放入堆中，重复执行下列操作 \(k\) 次：
- 取出堆顶状态 \(S\)，计算 \(S\) 的答案。
- 将 \(\operatorname{trans}(S)\) 中的状态放入堆中。
可以注意到，如果 \(|\operatorname{trans}(S)|\) 的大小是 \(O(1)\) 的，且都劣于 \(S\)，而且每个状态只会出现在一个 \(\operatorname{trans}\) 中，不重不漏（相当于若将 \(S\to \operatorname{trans}(S)\) 连边，构成一个外向森林，离根越远的状态越劣）时，算法是正确的。所以接下来需要考虑如何构造 \(\operatorname{trans}\)。
Part 1. Multiset
- 给定一个可重集 \(S\)，求大小为 \(p\) 的第 \(k\) 小子集和。
首先排序，最优状态一定是选排序后的前 \(p\) 项。
考虑每次转移，即将状态中的一个数替换为另一个数，设一个状态 \((x,y,z)\) 为选择前 \([1,x]\) 个数，目前考虑第 \(y\) 个数，且第 \(y\) 个数后面第一个选择的数是 \(z\)。\(z\) 及以后的数就都已经固定好了，不会再考虑。转移是 \((x,y,z)\to (x,y+1,z)\)（即选择目前考虑的数的下一位），\((x,y,z)\to(x-1,x+1,y)\)（即从前面 \([1,x]\) 中的数取出一个作为目前考虑的数，把之前考虑的数放到后面去不再考虑）。当然要合法才能转移。
初始把 \((p,n+1,n+1)\) 放到堆中。
- 给定一个可重集 \(S\)，求大小在 \([l,r]\) 之间的第 \(k\) 小子集和。
初始把 \((l,n+1,n+1)\sim (r,n+1,n+1)\) 放到堆中即可。
- 给定一个可重集 \(S\)，求第 \(k\) 小子集和，可以为空。
依然可以延续 2. 的做法。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 10;
int n, k;
typedef long long ll;
ll w[N], s;
struct node{
ll val;
int x, y, z;
bool operator < (const node &y) const {
return val > y.val;
}
node(ll v, int X, int Y, int Z){
val = v;
x = X;
y = Y;
z = Z;
}
};
int main(){
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++ i){
scanf("%lld", &w[i]);
}
sort(w + 1, w + n + 1);
priority_queue<node> q;
ll sum = 0;
for(int i = 0; i <= n; ++ i){//[l,r] 在这里改就行
sum += w[i];
q.push(node(sum, i, n+1, n+1));
}
while(k--){
auto p = q.top();
q.pop();
printf("%lld\n", p.val + s);
if(p.y + 1 < p.z){
q.push(node(p.val-w[p.y]+w[p.y+1], p.x, p.y+1, p.z));
}
if(p.x >= 1 && p.x + 1 < p.y){
q.push(node(p.val-w[p.x]+w[p.x+1], p.x-1, p.x+1, p.y));
}
}
return 0;
}
但是还有一种更简单的做法：状态中只有 \((x)\)，转移由 \((x)\to(x+1)\)，但是要分保不保留 \(x\) 位置上的这个数转移两种。注意这个做法不能处理集合中有负数的情况，可以将负数取反，并且答案减去负数的和。这样的话，对于负数 \(j\)，如果没选 \(|j|\)，减去负数和之后相当于选了 \(j\)；选了 \(|j|\)，那么与负数和之中的那个 \(j\) 抵消了，相当于没选。那么就解决了负数的问题。
Part 2. Arrays
\(n\) 个数组，每个数组中选 \(1\) 个，求第 \(k\) 小和。、
将所有数组排序，初始状态显然应当为全部取第一个。
状态设计为 \((x,y)\) 表示考虑了前 \(x\) 个数组，第 \(x\) 个数组取第 \(y\) 个，后面的数组都取第 \(1\) 个，转移为 \((x,y)\to (x,y+1), (x,y)\to(x+1,1)\)。但是我们考虑：对于第一个数组取第 \(2\) 个，后面都取第 \(1\) 个这样类似的方案会统计多次。所以要改变转移方法，强制每个状态计算时 \(y\) 不能为 \(1\)。
具体地，我们强制每次考虑下一个数组时转移为 \((x,y)\to(x+1,2)\)；那如果要求 \(x\) 数组取第一个怎么办？那就从 \((x,2)\) 转移到 \((x+1,2)\) 中新增一个转移，权值增加 \((a_{x+1,2}-a_{x+1,1})-(a_{x,2}-a{x,1})\)。所以在对数组内部排序的同时还要按 \(a_2-a_1\) 对所有数组之间进行排序。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int n, nn, k;
ll sum, ans;
struct arr{
int m, p[13];
} a[N];
bool cmp(arr x, arr y){
return x.p[2] - x.p[1] < y.p[2] - y.p[1];
}
struct state{
ll val;
int x, y;
bool operator < (const state &y) const {
return val > y.val;
}
state(ll v, int X, int Y){
val = v;
x = X;
y = Y;
}
};
int main(){
scanf("%d%d", &n, &k);
for(int i = 1; i <= n; ++ i){
int mm = 0;
scanf("%d", &mm);
if(mm == 1){
int p;
scanf("%d", &p);
sum += p;
} else {
++ nn;
a[nn].m = mm;
for(int j = 1; j <= a[nn].m; ++ j){
scanf("%d", &a[nn].p[j]);
}
sort(a[nn].p + 1, a[nn].p + a[nn].m + 1);
sum += a[nn].p[1];
}
}
sort(a + 1, a + nn + 1, cmp);
priority_queue<state> q;
q.push(state(sum, 0, 0));
while(k--){
auto p = q.top();
q.pop();
ans += p.val;
if(p.x && p.y + 1 <= a[p.x].m){
q.push(state(p.val + a[p.x].p[p.y+1] - a[p.x].p[p.y], p.x, p.y+1));
}
if(p.x < nn){
q.push(state(p.val + a[p.x+1].p[2] - a[p.x+1].p[1], p.x+1, 2));
}
if(p.y == 2 && p.x < nn){
ll tmp = a[p.x+1].p[2] - a[p.x+1].p[1] - (a[p.x].p[2] - a[p.x].p[1]);
q.push(state(p.val + tmp, p.x+1, 2));
}
}
printf("%lld\n", ans);
return 0;
}