Codeforces

分析

贪心地想可以知道，主席一定优先做 $b$ 最大的，如果 $b$ 相同会做 $a$ 最小的。

那么我们把所有任务排序，使得优先级越高的越靠后。

现在假设我们选了 $p$ 个任务出来，那么一定存在一条分界线，使得线前的主席都不做，线后的主席都做。

于是我们可以枚举分界线的位置，然后选出线前 $b$ 最大的 $p-k$ 个和线后 $a$ 最大的 $k$ 个，这就是这条线的答案。然后只要取最大的那个就好了。

线前 $b$ 最大的 $p-k$ 个很好维护，因为我们已经按优先级排序了，所以 $b$ 最大的 $p-k$ 个就是最后的 $p-k$ 个。和可以通过前缀和求出。

线后 $a$ 最大的 $k$ 个比较麻烦。因为我们只需要知道最大的 $k$ 个的和，所以可以预处理后缀的答案，拿一个小根堆维护即可。

这样子我们就能知道答案对应的分界线，那么就很好找到选了哪些了。

细节有一点点多。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;

int n,p,k;
struct data { int a,b,id; } a[N];
inline int cmp(data a,data b) {
    if (a.b!=b.b) return a.b<b.b;
    else return a.a>b.a;
}
bool operator <(data a,data b) { return a.a>b.a; }
priority_queue<int,vector<int>,greater<int> > Q;
priority_queue<data> Q2;
ll sa[N],sb[N];
ll ansa,ansb; int anspos;

int main() {
    n=read(),p=read(),k=read();
    for (re int i=1;i<=n;++i) a[i]=(data){read(),read(),i};
    sort(a+1,a+n+1,cmp);
    for (re int i=1;i<=n;++i) sb[i]=sb[i-1]+a[i].b;
    for (re int i=n;i>=n-k+1;--i) Q.push(a[i].a),sa[i]=sa[i+1]+a[i].a;
    for (re int i=n-k;i>=1;--i) {
        sa[i]=sa[i+1];
        if (a[i].a>Q.top()) {
            sa[i]-=Q.top(),Q.pop();
            sa[i]+=a[i].a,Q.push(a[i].a);
        }
    }
    for (re int i=p-k;i<=n-k+1;++i) {
        ll na=sa[i+1],nb=sb[i]-sb[i-(p-k)];
        if (na>ansa) ansa=na,ansb=nb,anspos=i;
        else if (na==ansa&&nb>ansb) ansb=nb,anspos=i;
    }
    for (re int i=anspos-(p-k)+1;i<=anspos;++i) printf("%d ",a[i].id);
    for (re int i=n;i>=n-k+1;--i) Q2.push(a[i]);
    for (re int i=n-k;i>anspos;--i)
        if (a[i].a>Q2.top().a) Q2.pop(),Q2.push(a[i]);
    while (Q2.size()) printf("%d ",Q2.top().id),Q2.pop();
    puts("");
    return 0;
}