题目链接:https://ac.nowcoder.com/discuss/437998
题目大意:
图片说明
思路:我们按价值排序,枚举中位数,那么中位数左右选择大小最小的m/2(m/2-1)个数。如果和<=s那么可以满足条件。
现在就是预处理s1[i]:1-i选择m个物品,价值最小的和。s[i]:n-i选择m个物品,价值最小的和。
我们用优先队列来维护m个最小的和。预处理后就枚举。

m是奇数:那么枚举的数就是中位数。
m是偶数:我们希望右边的最小值越小越好。并且s2[i]:从1-n一定是单调递增。那么我们二分下。右边选取的位置就可以了。

#include <bits/stdc++.h>
#define LL long long
using namespace std;

struct node{
    LL a, b;
}a[100005];
LL s1[100005], s2[100005];
priority_queue<LL> q;

LL slove(LL l, LL r, LL x){

    LL ans=-1;
    while(l<=r){
        LL mid=l+r>>1;
        if(s2[mid]<=x){
            l=mid+1;
            ans=a[mid].a;
        }
        else{
            r=mid-1;
        }
    }
    return ans;
}

int main(){
    LL v, n, m; scanf("%lld%lld%lld", &v, &n, &m);
    LL pos=!(m%2); m/=2;
    for(int i=1; i<=n; i++){
        scanf("%lld%lld", &a[i].a, &a[i].b);
    }
    sort(a+1, a+1+n, [](node &a, node &b){return a.a<b.a;});
    for(int i=1; i<=n; i++){//预处理左半部分
        q.push(a[i].b), s1[i]+=s1[i-1]+a[i].b;
        if(q.size()>m-pos){
            s1[i]-=q.top(); q.pop();
        }
    }
    while(!q.empty()) q.pop();
    for(int i=n; i>=1; i--){//预处理右半部分
        q.push(a[i].b), s2[i]+=s2[i+1]+a[i].b;
        if(q.size()>m){
            s2[i]-=q.top(); q.pop();
        }
    }
    LL ans=*0;
    if(!pos){
        for(int i=m+1; i<=n-m; i++){
            if(s1[i-1]+s2[i+1]+a[i].b<=v){
                ans=a[i].a;
            }
        }
        printf("%lld\n", ans);
    }
    else{
        for(int i=m; i<=n-m; i++){
            LL s=slove(i+1, n-m+1, v-s1[i-1]-a[i].b);
            if(ans!=-1){
                ans=max(ans, a[i].a+s);
            }
        }
        printf("%lld\n", ans/2);
    }

    return 0;
}