[TJOI2013]奖学金乱搞

从\(c\)个二元组\((v,w)\)中选出\(n\)个，使其\(v\)的中位数最大的同时使\(w\)和小于等于\(f\)，求这个中位数

有点意思。有点像二分答案的思路，枚举中位数，将原问题转换为一个判定问题，贪心选择中位数之前\(w\)最小的\((n-1)/2\)个，之后\(w\)最小的\((n-1)/2\)个，然后判断一下是否小于等于\(f\)即可。

使用优先队列贪心即可。

#include <cstdio>

#include <algorithm>

#include <queue>

#define MAXN 200002

using namespace std;

int n,c,mx;

priority_queue <int> q;

struct nod{

    int s,w;

} a[MAXN];

bool cmp(const nod &a, const nod &b){

    return a.s<b.s;

}

int sum;

int f[MAXN],g[MAXN];

int main(){

    scanf("%d %d %d", &n, &c, &mx);

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

        scanf("%d %d", &a[i].s, &a[i].w);

    sort(a+1, a+1+c, cmp);

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

        sum+=a[i].w;

        q.push(a[i].w);

    }

    //f[i] <i min cost

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

        f[i]=sum;

        int top=q.top();

        if(top>a[i].w){

            q.pop();

            sum-=top;

            sum+=a[i].w;

            q.push(a[i].w);

        }

    }

    sum=0;

    while(!q.empty()) q.pop();

    for(int i=c;i>=c-n/2+1;--i){

        sum+=a[i].w;

        q.push(a[i].w);

    }

    //g[i] >i min cost

    for(int i=c-n/2;i>=1;--i){

        g[i]=sum;

        int top=q.top();

        if(top>a[i].w){

            q.pop();

            sum-=top;

            sum+=a[i].w;

            q.push(a[i].w);

        }

    }

    for(int i=c-n/2;i>=n/2+1;--i)

        if(a[i].w+f[i]+g[i]<=mx){

            printf("%d", a[i].s);

            return 0;

        }

    puts("-1");

    return 0;

}

巴特西

[TJOI2013]奖学金乱搞

[TJOI2013]奖学金乱搞

最新文章

热门文章

巴特西

[TJOI2013]奖学金 乱搞

[TJOI2013]奖学金 乱搞

最新文章

热门文章

[TJOI2013]奖学金乱搞

[TJOI2013]奖学金乱搞