Smallest Subsets

传送门

题意：\(n\le 1e5\) 个整数，范围 \(-1e9\le a\le 1e9\)，求第 \(k\) 小的子集和

思路

先考虑只有正数怎么做

这就是经典的类最短路：

先将序列排序，然后从最小的子集和 \({a_1}\) 出发

每次加入 \(S-a_{Mx}+a_{Mx+1}\) 和 \(S+a_{Mx+1}\)，其中 \(Mx\) 表示 \(S\) 中最大数的下标

维护一个优先队列，每次弹出 \(k\) 以后的元素即可

再来考虑有负数的情况

假设序列中的所有负数和为 \(minus\)

那显然我们是从 \(minus\) 出发，每次加上一个正数，或者去掉一个负数

那我们可以考虑将所有负数先取反变成正数，按照上面的方法跑一遍，最后每个求出来的子集和都加上 \(minus\) 即可

代码

#include<iostream>
#include<fstream>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<map>
#include<set>
#include<bitset>
#define LL long long
#define FOR(i, x, y) for(int i = (x); i <= (y); i++)
#define ROF(i, x, y) for(int i = (x); i >= (y); i--)
#define PFOR(i, x) for(int i = he[x]; i; i = r[i].nxt)
inline int rd()
{
    int sign = 1, re = 0; char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') sign = -1; c = getchar();}
    while('0' <= c && c <= '9'){re = re * 10 + (c - '0'); c = getchar();}
    return sign * re;
}
int n, m, a[100005];
LL minus, ans;
#define pli std::pair<LL, int>
std::multiset<pli> q;
signed main()
{
#ifndef ONLINE_JUDGE
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif
    n = rd(), m = rd() - 1;
    FOR(i, 1, n)
    {
        a[i] = rd();
        if(a[i] < 0) minus += a[i], a[i] = -a[i];
    }
    printf("%lld\n", minus);
    std::sort(a + 1, a + 1 + n);
    q.insert(pli(a[1], 1));
    while(m)
    {
        ans = (*q.begin()).first;
        printf("%lld\n", ans + minus);
        int pos = (*q.begin()).second;
        if(pos < n)
        {
            LL sum = ans - a[pos] + a[pos + 1];
            q.insert(pli(sum, pos + 1));
            sum = ans + a[pos + 1];
            q.insert(pli(sum, pos + 1));
        }
        m--; q.erase(q.begin());
    }
    return 0;
}