大顶堆+动态规划+二分

前言：我们这一题需要分类讨论
对于我们左边和右边的我们需要预处理
有点类似反悔堆的做法，得出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;
}