TJOI2013奖学金|题解

小张最近发表了一篇论文,有一个神秘人物要给小张学院发奖学金。小张学院有C名学生,要从中挑出N个。这个神秘人物爱好奇特,他希望得到奖学金的同学的成绩的中位数尽可能大,但同时,他们的奖学金总额不能超过F。

观察题目,显然应当将学生依照成绩排序

当成绩中位数确定时,应选取中位数两侧金额最小的学生,满足贪心原则

题意转化为

求中位数两端学生中金额前n/2小的金额之和

区间第k小问题,显然选用主席树解答

从大到小枚举中位数,选取第一个满足条件的即可

注意:

本题对空间要求严格,

如果预先求出所有从0开始的前缀和和从c开始的所有后缀和的树版本,必然MLE(亲测)
如果只预处理前(后)缀和树,另一部分用完整树与之相减,且在枚举中位数时动态建树,可以勉强卡过(笔者的解法)
注意到中位数无法二分枚举,所以实际上只用到了当前版本和上一个版本的树,更早的树应当被销毁!

所以当笔者写完后发现根本不需要主席树……..

笔者代码如下(注意数据命名与题面不符):

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#define llint long long
using namespace std;
int set_[200010],cnt[200010];
struct node{
        node *lson,*rson;
        int val,sum_;
        node(int ql,int qr,bool full){
                // build a void tree
                if(ql == qr){
                        lson = rson = NULL;
                        val = full * cnt[ql];sum_ = val * set_[ql];
                }
                else{
                        int mid = ((qr - ql) >> 1) + ql;
                        lson = new node(ql,mid,full);
                        rson = new node(mid + 1,qr,full);
                        val = full * (lson->val + rson->val);
                        sum_ = full * (lson->sum_ + rson->sum_);
                }
        }
        node(node *ori,node *ls,node *rs,int ival){
                lson = ls;rson = rs;
                val = ori->val + 1;sum_ = ori->sum_ + set_[ival];
        }
        node* insert(int ival,int l,int r){
                int mid = ((r - l) >> 1) + l;
                if (ival == l && ival == r)
                        return new node(this,NULL,NULL,ival);
                if (ival <= mid)
                        return new node(this,lson->insert(ival,l,mid),rson,ival);
                else 
                        return new node(this,lson,rson->insert(ival,mid + 1,r),ival);
        }


}*full,*suf[200010];
int query(node *op,int k,int l,int r){
        int mid = ((r - l) >> 1) + l;
        if (l == r)
                return k * set_[l];
        if (k <= op->lson->val)
                return query(op->lson,k,l,mid);
        else 
                return op->lson->sum_ + query(op->rson,k - op->lson->val,mid + 1,r);
}
int query2(node *op,node *ff,int k,int l,int r){
        int mid = ((r - l) >> 1) + l;
        if (l == r)
                return k * set_[l];
        if (k <= ff->lson->val - op->lson->val)
                return query2(op->lson,ff->lson,k,l,mid);
        else 
                return ff->lson->sum_ - op->lson->sum_ + query2(op->rson,ff->rson,k -(ff->lson->val -  op->lson->val),mid + 1,r);
}

struct xxx{
        int score,money;
        bool operator < (const xxx &be)const{
                return score < be.score;
        }
}data[200010];
int main (){
//      freopen("wb.in","r",stdin);
        //readin
        int n,k,p;
        cin>> k >> n >> p;
        for (int i = 1;i <= n;++ i){
                scanf("%d%d",&data[i].score,&data[i].money);
        }
        sort(data + 1,data + 1 + n);
        //discrete
        for (int i = 1;i <= n;++ i)
                set_[i] = data[i].money;
        sort(set_ + 1,set_ + 1 + n);
        int size_ = unique(set_ + 1,set_ + 1 + n) - set_ - 1;
        for (int i = 1;i <= n;++ i)
                data[i].money = lower_bound(set_ + 1,set_ + size_ + 1,data[i].money) - set_,
                cnt[data[i].money] ++;
        //build trees
        suf[n + 1] = new node (1,size_,0);
        full = new node (1,size_,1);
        for (int i = n;i > n - (k >> 1);-- i)
                suf[i] = suf[i + 1]->insert(data[i].money,1,size_);
        //query
        for (int i = n - (k >> 1);i > (k >> 1);-- i){
                suf[i] = suf[i + 1]->insert(data[i].money,1,size_);
                if(query2(suf[i],full,k >> 1,1,size_) + query(suf[i + 1],k >> 1,1,size_) + set_[data[i].money] <= p){
                        cout << data[i].score;
                        return 0;
                }
        }
        cout << -1 ;
        return 0;
}

以上.