SCUT - 131 - 小P玩游戏II - 贪心

https://scut.online/p/131

首先假如钦定了一群人去打怪兽，那么可以把主要的任务都丢给b最大的人去打，这样不会更差。然后考虑枚举这个b最大的人，其他人陪练。一开始就是ai+k*bi+sumC-ci，这个很好理解，然后这个人分出至多t=k-1个怪兽给陪练团打，那么既然规定陪练团每个人只能选1只去打，那么肯定是贪心选vj=aj+bj-cj最大的t个人去打。搞个Treap（随便，但是WA了好多发）维护一下。

注意是我这个模板居然没有初始化，草，还要自己写。但是Treap具体的原理并不是很明白。

注意的WA点在于找不超过k个人，且v要大于bi的那堆和。当右子树为空并不代表可以退出，或者说，当现在进入第二个分类里面的时候，有可能这里的子树是有用的。

看见别人直接二分找，内心是一千个草泥马。唉就当学习一下平衡树。

注意空间要开双倍，因为insert有两次。除非弄个回收？回收很好办的，实测省略一点点空间。因为经过直觉最多同时存在n个点所以直接这样就可以了：搞个STLstack（不能用数组否则不是浪费自己表情？）newnode的时候从stack里面删除，remove的时候把id放回stack里面。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 200000;

int ch[MAXN + 5][2];

int val[MAXN + 5], dat[MAXN + 5];

int siz[MAXN + 5], cnt[MAXN + 5];

ll sum[MAXN + 5];

int tot, root;

inline void Init() {

    tot = 0;

    root = 0;

}

inline int NewNode(int v) {

    ch[++tot][0] = 0;

    ch[tot][1] = 0;

    val[tot] = v, dat[tot] = rand();

    siz[tot] = 1, cnt[tot] = 1;

    sum[tot] = v;

    return tot;

}

inline void PushUp(int id) {

    siz[id] = siz[ch[id][0]] + siz[ch[id][1]] + cnt[id];

    sum[id] = sum[ch[id][0]] + sum[ch[id][1]] + 1ll * val[id] * cnt[id];

}

inline void Rotate(int &id, int d) {

    int temp = ch[id][d ^ 1];

    ch[id][d ^ 1] = ch[temp][d];

    ch[temp][d] = id;

    id = temp;

    PushUp(ch[id][d]), PushUp(id);

}

inline void Insert(int &id, int v) {

    if(!id)

        id = NewNode(v);

    else {

        if(v == val[id])

            ++cnt[id];

        else {

            int d = v < val[id] ? 0 : 1;

            Insert(ch[id][d], v);

            if(dat[id] < dat[ch[id][d]])

                Rotate(id, d ^ 1);

        }

        PushUp(id);

    }

}

void Remove(int &id, int v) {

    if(!id)

        return;

    else {

        if(v == val[id]) {

            if(cnt[id] > 1) {

                cnt[id]--;

                PushUp(id);

            } else if(ch[id][0] || ch[id][1]) {

                if(!ch[id][1] || dat[ch[id][0]] > dat[ch[id][1]])

                    Rotate(id, 1), Remove(ch[id][1], v);

                else

                    Rotate(id, 0), Remove(ch[id][0], v);

                PushUp(id);

            } else

                id = 0;

        } else {

            v < val[id] ? Remove(ch[id][0], v) : Remove(ch[id][1], v);

            PushUp(id);

        }

    }

}

ll GetSum(int bi, int k) {

    if(k == 0)

        return 0;

    //把大于bi的最大的至多k个v全部加起来，每加一个减去一个bi

    int r = root;

    ll res = 0;

    while(r) {

        if(bi >= val[r] || (ch[r][1] && siz[ch[r][1]] >= k)) {

            //bi不比这个节点小，这个节点没用，向右走

            //或者前k大完全在右子树中

            r = ch[r][1];

            continue;

        } else {

            //有用的完全在该节点及其右子树中

            /*if(!ch[r][1])

                return res;*/

            res += sum[ch[r][1]];

            res -= 1ll * siz[ch[r][1]] * bi;

            k -= siz[ch[r][1]];

            if(k <= cnt[r]) {

                res += 1ll * k * (val[r] - bi);

                k = 0;

                return res;

            }

            else{

                res += 1ll * cnt[r] * (val[r] - bi);

                k -=cnt[r];

            }

            r=ch[r][0];

        }

    }

    return res;

}

int n, k;

struct Char {

    int a, b, c;

    int v;

    Char() {};

    Char(int _a, int _b, int _c) {

        a = _a;

        b = _b;

        c = _c;

        v = a + b - c;

    }

} cha[100005];

ll sumC;

ll calc(int id) {

    ll M = sumC - cha[id].c + cha[id].a + 1ll * k * cha[id].b  ;

    Remove(root, cha[id].v);

    //至多从平衡树拿走k-1个

    ll res = GetSum(cha[id].b, k - 1);

    Insert(root, cha[id].v);

    return M + res;

}

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

#endif // Yinku

    int T;

    scanf("%d", &T);

    while(T--) {

        scanf("%d%d", &n, &k);

        sumC = 0;

        Init();

        for(int i = 1; i <= n; ++i) {

            int a, b, c;

            scanf("%d%d%d", &a, &b, &c);

            cha[i] = Char(a, b, c);

            sumC += c;

            Insert(root, cha[i].v);

        }

        ll ans = 0;

        for(int i = 1; i <= n; ++i)

            ans = max(ans, calc(i));

        printf("%lld\n", ans);

    }

    return 0;

}

巴特西

SCUT - 131 - 小P玩游戏II - 贪心 - 平衡树

最新文章

热门文章