最后翻看题解才发现可以不用主席树……就当是练习好了
基本思路
本题要让中位数最大，如果是最小值最大我们可以用二分答案，二中位数最大可不可以呢？显然是不行的，所以我们枚举中位数，判定是否可行。
本题中，\(n\)为奇数。根据贪心，在比中位数大的数据中选\((n-1)/2\)小值，比中位数小的数中也如此，如此一来变成了一道静态区间\(k\)小值和问题，如果按\(a\)数组排序，则数值大小转化为了下标大小，理解起来更容易
静态区间\(k\)小值和问题可以用主席树解决，是一道经典问题
代码
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,c,f;
struct node {
int a,b;
}q[N];
bool cmp(node a,node b) {
return a.a<b.a;
}
int diff[N],len;
int get(int x) {
return lower_bound(diff+1,diff+len+1,x)-diff;
}
//主席树
struct segt{
int lc,rc;
int siz,sum; //维护子树大小（k值用），子树和（区间和用）
}t[N<<5];
int root[N],cnt;
int push_up(int p) {
t[p].siz=t[t[p].lc].siz+t[t[p].rc].siz;
t[p].sum=t[t[p].lc].sum+t[t[p].rc].sum;
}
int clone(int p) {
t[++cnt]=t[p];
return cnt;
}
int build(int p,int L,int R) {
p=++cnt;
if(L==R)
return p;
int mid=(L+R)>>1;
t[p].lc=build(p,L,mid);
t[p].rc=build(p,mid+1,R);
return p;
}
int change(int p,int L,int R,int idx,int k) {
p=clone(p);
if(L==R) {
t[p].siz+=1;
t[p].sum+=k;
return p;
}
int mid=(L+R)>>1;
if(idx<=mid) t[p].lc=change(t[p].lc,L,mid,idx,k);
else t[p].rc=change(t[p].rc,mid+1,R,idx,k);
push_up(p);
return p;
}
int query(int p1,int p2,int L,int R,int k) {
if(L==R) return k*diff[L]; //注意此处，k不一定能覆盖整个区间，可能只能取区间中一部分值
int p=t[t[p2].lc].siz-t[t[p1].lc].siz;
int mid=(L+R)>>1;
if(p==k)
return t[t[p2].lc].sum-t[t[p1].lc].sum;
if(p<k)
return t[t[p2].lc].sum-t[t[p1].lc].sum+query(t[p1].rc,t[p2].rc,mid+1,R,k-p);
return query(t[p1].lc,t[p2].lc,L,mid,k);
}
int main() {
scanf("%d%d%d",&n,&c,&f);
for(int i=1;i<=c;i++) {
scanf("%d%d",&q[i].a,&q[i].b);
diff[++len]=q[i].b;
}
sort(q+1,q+c+1,cmp);
sort(diff+1,diff+len+1);
len=unique(diff+1,diff+len+1)-diff-1;
for(int i=1;i<=c;i++)
q[i].b=get(q[i].b);
root[0]=build(1,1,len);
for(int i=1;i<=c;i++)
root[i]=change(root[i-1],1,len,q[i].b,diff[q[i].b]);
int ans=-1;
for(int i=n/2+1;i<=c-n/2;i++) {
int p=query(root[0],root[i-1],1,len,n/2)+query(root[i],root[c],1,len,n/2)+diff[q[i].b];
if(p<=f) ans=max(ans,q[i].a);
}
printf("%d",ans);
return 0;
}