NC17315 背包（优先队列+二分）

这题奇数部分比较容易想到，用优先队列维护每个位置前能否取到指定个数，这样枚举每个位置座位中位数即可

对于偶数，由于两个数位置不确定，并且不能枚举两个，因此还是考虑要维护一个

这样就需要一个log复杂度以内的算法找到每个对应的最优解，常见的就是二分算法

我们观察题目性质，果然符合单调性，因为对于左边定好的数，第二个肯定越右越好，并且我们知道越右满足条件的难度越大，因此考虑二分找到最右点

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const int N=2e5+10;
const int inf=1e9;
const int mod=1e9+7;
ll v,n,m;
ll pre[N],suf[N];
priority_queue<ll> q;
struct node{
    ll a,b;
}s[N];
bool cmp(node a,node b){
    return a.a<b.a;
}
int main(){
    ios::sync_with_stdio(false);
    int i;
    ll sum=0;
    cin>>v>>n>>m;
    for(i=1;i<=n;i++){
        cin>>s[i].a>>s[i].b;
    }
    sort(s+1,s+1+n,cmp);
    for(i=1;i<=n;i++){
        pre[i]=pre[i-1]+s[i].b;
        q.push(s[i].b);
        while(q.size()>(m-1)/2){
            pre[i]-=q.top();
            q.pop();
        }
    }
    while(q.size())
        q.pop();
    for(i=n;i>=1;i--){
        suf[i]=suf[i+1]+s[i].b;
        q.push(s[i].b);
        if(q.size()>(m-1)/2){
            suf[i]-=q.top();
            q.pop();
        }
    }
    ll ans=0;
    if(m%2){
        for(i=n-(m-1)/2;i>(m-1)/2;i--){
            if(s[i].b+pre[i-1]+suf[i+1]<=v){
                ans=max(ans,s[i].a);
            }
        }
        cout<<ans<<endl;
    }
    else{
        for(i=(m-1)/2+1;i<n-(m-1)/2;i++){
            int l=i+1,r=n-(m-1)/2;
            int tmp=v-s[i].b-pre[i-1];
            while(l<=r){
                int mid=l+r>>1;
                if(suf[mid+1]+s[mid].b<=tmp){
                    ans=max(ans,(s[i].a+s[mid].a)/2);
                    l=mid+1;
                }
                else{
                    r=mid-1;
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}