51nod1821 最优集合贪心

首先考虑一个集合的最大优美值怎么求出

考虑新增一个数，假设我们现在的优美值已经达到了$V$，那么只需要一个$[1, V + 1]$的数就可以使$V$达到更大

为了保证能添加尽可能多的数进来，我们这么构造：

对集合$S$排序，从小到大选择，直到选到$sumlimits_{i = 1}^{j}v[j] + 1 < v[j]$的$v[j]$，退出

为什么这么做正确呢？

如果不正确，只可能存在一个数$S$可以被大于一个数的和表示，并且满足$v[S] > V + 1$

其中$v[S]$表示构成$S$的所有$v$，$V$表示现在选出的和

由于整数的离散性，因此，一定有$v[S] leqslant V + 1$，所以不可能不正确...

（很sb的证明....）

现在有两个集合了

只要进行这么一种操作$k$次就好了，记$W$表示从$S2$中选出的数的和，$S$表示目前$S1$中选出的数的和

1.找出使得$sumlimits_{i = 1}^{k - 1} v[i] + W + 1 < v[k]$成立的最大的$k$，令$S = sumlimits_{i = 1}^{k - 1} v[i]$

2.再找出最大的且没有被选择的$j$使得$v[j] leqslant W + S + 1$成立，之后选择$j$，$W += v[j]$，拿个栈维护即可

重复$k$次即可得出最后的结果

复杂度$O(Tm)$

注：那个㧟我快读的人拿rk3~~有猫病~~.....

注2：反正我还是rk1

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

extern inline char gc() {
    static char RR[23456], *S = RR + 23333, *T = RR + 23333;
    if(S == T) fread(RR, 1, 23333, stdin), S = RR;
    return *S ++;
}
inline int read() {
    int p = 0, w = 1; char c = gc();
    while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); }
    while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();
    return p * w;
}

int wr[50], rw;
#define pc(x) *O ++ = x
char WR[50000005], *O = WR;
inline void write(long long x) {
    if(!x) pc('0');
    if(x < 0) x = -x, pc('-');
    while(x) wr[++ rw] = x % 10, x /= 10;
    while(rw) pc(wr[rw --] + '0'); pc('
');
}

#define sid 1005
#define ri register int
#define ll long long

int n, T, tt;
int num[sid], q[sid], S[sid][sid];

int main() {
    n = read();
    for(ri i = 1; i <= n; i ++) {
        num[i] = read();
        for(ri j = 1; j <= num[i]; j ++) S[i][j] = read();
        sort(S[i] + 1, S[i] + num[i] + 1);
    }
    T = read();
    for(ri i = 1; i <= T; i ++) {
        int a = read(), b = read(), k = min(read(), num[b]);
        int *A = S[a], *B = S[b];
        ll ans = 0; ri ia = 1, ib = 1; tt = 0;
        while(k) {
            while(A[ia] <= ans + 1 && ia <= num[a]) ans += A[ia], ia ++;
            while(B[ib] <= ans + 1 && ib <= num[b]) q[++ tt] = B[ib], ib ++;
            if(!tt) break; ans += q[tt --]; k --;
        }
        while(A[ia] <= ans + 1 && ia <= num[a]) ans += A[ia], ia ++;
        write(ans);
    }
    fwrite(WR, 1, O - WR, stdout);
    return 0;
}

51nod1821 最优集合 贪心

相关推荐

51nod1821 最优集合贪心