Codeforces 1251E Voting

E2. Voting (Hard Version)

题意: 有n个人, 你想让他们都给你投票. 你可以选择花费pi收买第i个人, 或者如果有mi个人已经给你投票了, 那么第i个人会自动给你投票.

不妨把题目等价为, 给n个人排一个先后投票的顺序, 假设在这个顺序中, 第k个投票的人, 它的mi不超过k-1, 那么这个人就不需要花钱收买, 否则就需要花钱收买.

那么我们依次考虑第1,2,3,....n个投票的位置让哪个人来投票. 可以发现, 只要我们让"不需要花钱收买的人省下的钱"最大化, 就相当于让代价最小化了.

对于每个位置, 最优化这个位置的收益. 而且越靠前的位置越无用, 所以我们从前往后依次考虑每个位置, 最大化每个位置的收益, 也就是在每个位置考虑能在这个位置避免花钱收买的人, 把其中花钱最多的人放到这个位置. 借助一个堆来实现即可.

#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

typedef long long i64;

const int maxn = 200005;

struct vote{

    int m, p;

    bool operator < (const vote &b)const{

        return m < b.m;

    }

}V[maxn];

void work(){

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

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

        scanf("%d%d", &V[i].m, &V[i].p);

    }

    sort(V+1, V+n+1);

    priority_queue<int> q;

    i64 ans = 0;

    int pt = 1;

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

        while(pt <= n && V[pt].m<=i){

            ans += V[pt].p;

            q.push(V[pt].p);

            ++pt;

        }

        if(!q.empty()){

            ans -= q.top();

            q.pop();

        }

    }

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

}

int main(){

    int t;scanf("%d", &t);

    while(t--)work();

    return 0;

}

巴特西

Codeforces 1251E Voting

最新文章

热门文章