[ABC281E] Least Elements 题解

FFTotoro · 2022-12-11 12:52:21 · 题解

前言

赛时做出了 E 却没做出 D。

解法

首先用一个 std::vector（记为 b） 存储前 M 个数，排序后取前 k 大，这就是第一个询问的答案，记为 c。

对于接下来每一个询问，我们只需用 lower_bound 函数二分出需要删除的那个数（设为 r）的位置，并判断删掉它会不会对答案有影响。如果有影响，那么 c\leftarrow c+b_{K+1}-r 并删除它。

然后考虑插入一个新的数，设为 p。同样地，用 insert 结合 upper_bound 插入后再次查询排名（有一大佬指出，insert 函数插入常数极小），考虑对答案有没有影响，如果有影响，那么 c\leftarrow c+p-b_{K+1}。

每次询问输出处理过的 c 即可。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int n,m,k,c=0; cin>>n>>m>>k;
  vector<int> a(n),b;
  for(auto &i:a)cin>>i;
  for(int i=0;i<m;i++)b.emplace_back(a[i]);
  sort(b.begin(),b.end());
  for(int i=0;i<k;i++)c+=b[i]; // 先处理出第一个答案
  cout<<c<<' ';
  for(int i=1;i<=n-m;i++){
    auto l=lower_bound(b.begin(),b.end(),a[i-1]); // 查询需要删除的数的 rank
    if(l-b.begin()<k)c+=b[k]-*l; b.erase(l); // 有影响
    b.insert(upper_bound(b.begin(),b.end(),a[i+m-1]),a[i+m-1]); // 插入
    auto r=lower_bound(b.begin(),b.end(),a[i+m-1]); // 插入后查询 rank
    if(r-b.begin()<k)c+=a[i+m-1]-b[k]; // 有影响
    cout<<c<<' ';
  }
  cout<<endl;
  return 0;
}