大顶堆+动态规划+二分
前言:我们这一题需要分类讨论
对于我们左边和右边的我们需要预处理
有点类似反悔堆的做法,得出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;
}