NC17315 背包(优先队列)

题目链接

题意：



题解：

AC代码

/*
    Author:zzugzx
    Lang:C++
    Blog:blog.csdn.net/qq_43756519
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define SZ(x) (int)x.size()
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod=1e9+7;
//const int mod=998244353;
const double eps = 1e-10;
const double pi=acos(-1.0);
const int maxn=1e6+10;
const ll inf=0x3f3f3f3f;
const int dir[4][2]={{0,1},{1,0},{0,-1},{-1,0}};

struct node{
    ll a,b;
}p[maxn];
bool cmp(node a,node b){
    return a.a<b.a;
}
ll s1[maxn],s2[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    ll v,n,m;
    cin>>v>>n>>m;
    for(int i=1;i<=n;i++)cin>>p[i].a>>p[i].b;
    sort(p+1,p+1+n,cmp);
    int x=m&1;m>>=1;
    priority_queue<ll> q;
    for(int i=1;i<=n;i++){
        q.push(p[i].b),s1[i]=s1[i-1]+p[i].b;
        if(q.size()>m-1+x)s1[i]-=q.top(),q.pop();
    }
    while(!q.empty())q.pop();
    for(int i=n;i;i--){
        q.push(p[i].b),s2[i]=s2[i+1]+p[i].b;
        if(q.size()>m)s2[i]-=q.top(),q.pop();
    }
    if(x){
        ll ans=0;
        for(int i=m+1;i<=n-m;i++)
            if(s1[i-1]+s2[i+1]+p[i].b<=v)ans=p[i].a;
        cout<<ans;
    }
    else{
        ll ans=0;
        for(int i=m;i<=n-m;i++){
            int l=i+1,r=n-m+1;
            while(l<=r){
                int mid=l+r>>1;
                if(s1[i-1]+s2[mid]+p[i].b<=v)l=mid+1;
                else r=mid-1;
            }
            if(r>i)ans=max(ans,p[i].a+p[r].a);
        }
        cout<<ans/2;
    }
    return 0;
}