大顶堆+动态规划+二分

前言：我们这一题需要分类讨论
对于我们左边和右边的我们需要预处理
有点类似反悔堆的做法，得出i之前取出 m 个元素代价最小，并且这个代价一定是递减的（可以推导一下）

题目地址

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

#define int long long
const int N = (int)1e5+10;
int v,n,m;
int le[N],rig[N];

struct node
{
    int va,wei;
    bool operator<(node b){
        return va<b.va;
    }
}sto[N];


signed main(){
    cin >> v >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> sto[i].va >> sto[i].wei;
    }
    sort(sto+1,sto+1+n);
    int x = (m&1); m/=2;
    priority_queue<int> q;
    int now = 0;
    for(int i=1;i<=n;i++){
        now += sto[i].wei; q.push(sto[i].wei);
        while(q.size()>m-1+x) now -= q.top(),q.pop();
        le[i] = now;
    }
    now = 0;
    while(q.size()) q.pop();
    for(int i=n;i;i--){
        now += sto[i].wei; q.push(sto[i].wei);
        while(q.size()>m) now -= q.top(),q.pop();
        rig[i] = now;
    }
    int ans = 0;
    if(x){
        for(int i=m+1;i<=(n-m);i++){
            if(le[i-1]+sto[i].wei+rig[i+1]<=v){
                ans = max(ans,sto[i].va);
            }
        }cout << ans;
    }else{
        for(int i=m;i<=(n-m);i++){
            // 左端点取 i
            // 开始二分 右端点
            int l = m , r = (n-m)+2;
            while(l+1<r){
                int mid = (l+r)/2;
                if(le[i-1]+sto[i].wei+rig[mid]<=v) l = mid;
                else r = mid;
            }
            //cout << " i " << i << " " << l << endl;
            if(l>i&&l<=(n-m)+1) ans = max(ans,sto[i].va+sto[l].va);
        }
        cout << ans/2;
    }
    system("pause");
    return 0;
}