题解 | # F. Mooclear Reactor 2 #

$[思维+贪心]$

首先，如果选择 $k$ 个粒子，那么这 $k$ 个粒子都需要满足 $y_{1\leq i \leq k} \geq k - 1$ ，即 $y_{1\leq i \leq k} + 1\geq k$

如果选取商店里的粒子 $(x_{0},y_{0})$ ，假设一共选择了 $k$ 个粒子，那么需要满足 $y_{0} \geq k$ ，其余了 $k -1$ 个粒子都需要满足 $y_{1 \leq i \leq k - 1} \geq k$ ，那么此时能量的最大值为 $x_{0} + max_{0 \leq i \leq y_{0}}(S[i])$

定义 $S[k]$ 表示原始粒子中所有满足 $y \geq k$ 的前 $k$ 大粒子的能量和

如果 $y \geq k$ 的粒子数小于 $k$ ，那么就是这全部粒子的能量和
如果 $y \geq k$ 的粒子数大于等于 $k$ ，那么取前 $k$ 大粒子的能量和

如何求 $S[k]$ ：

将 $k$ 从 $n$ 到 $1$ 按照从大到小的顺序遍历，这样满足已经放入的粒子仍然满足 $y\geq k$ ，现在需要维护前 $k$ 大的粒子能量和最大值，所以用优先队列模拟

使用小根堆，这样先 $push$ 进去，如果堆里面的元素数量多了，再取出堆顶最小的几个元素

总代码：

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;

    
priority_queue<int, vector<int>, greater<int> > q;
void solve(){

    while(q.size()) q.pop();
    int n, m; cin >> n >> m;
    vector<vector<int> > adj(n + 10);
    for(int i = 1; i <= n; i ++){
        int x, y; cin >> x >> y;
        adj[y].push_back(x);
    }    
    vector<int> a(n + 10);
    a[0] = 0;
    int sum = 0, ans = 0;
    for(int i = n; i >= 1; i --){
        for(int x : adj[i]){
            q.push(x);
            sum += x;
        }
        while((int)q.size() > i){
            sum -= q.top();
            q.pop();
        }
        a[i] = sum;
    }
    while(q.size()) q.pop();
    sum = 0;
    for(int i = n; i >= 0; i --){
        for(int x : adj[i]){
            sum += x;
            q.push(x);
        }
        while((int)q.size() > i + 1){
            sum -= q.top();
            q.pop();
        }
        ans = max(ans, sum);
    }
    vector<int> pre(n + 10);
    for(int i = 1; i <= n; i ++) pre[i] = max(pre[i - 1], a[i]);

    for(int i = 1; i <= m; i ++){
        int x, y; cin >> x >> y;
        cout << max(ans, x + pre[y]) << " ";
    }
    cout << endl;
    return ;
}

signed main(){
    HelloWorld;

    int tt = 1; 
    cin >> tt;
    while(tt --) solve();
    return 0;
}