ABC205 D - Kth Excluded

問題はこちら

• 問題概要
• 解説
• 提出プログラム
• 感想

問題概要

長さの正整数列が与えられる．以下の個のクエリに答えよ．

• 正整数が与えられる．のいずれとも異なる正整数のうち，小さい方から数えて番目のものを求めよ．

解説

クエリを先読みすることで二分探索を用いずに解きます．

まず，を昇順にソートします．の昇順に，以下のに含まれない正整数の数を管理します．例えば，だとは順にとなっていきます．
となるとき，番目の正整数はその地点より左側に存在することになるので処理を行うことができます．例として，だと，となる時点でとなっているのではとの間(両端は含まない)にあることが分かり，となる時点ではとなっているのではとの間にあることが分かります．
実装ではとした方が楽です．詳しくは以下のプログラムを参照してください．計算量はとなります．

提出プログラム

#include "bits/stdc++.h" 
using namespace std; 
typedef long long ll;

int main() {
    int n,q;cin >> n >> q;
    vector<ll> a(n),k(q),ans(q);
    vector<int> id(q); // id[i]:=昇順i番目のクエリの番号
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < q; i++) cin >> k[i];
    iota(id.begin(), id.end(),0);
    sort(id.begin(), id.end(),[&](int a,int b){return k[a]<k[b];});
    int t = 0;
    ll sum = 0,pre = 0;// sum:Aにない正整数の数 pre:ひとつ前のA_i
    for (int i = 0; i < n; i++) {
        // K <= S となるKをすべて処理
        while(t < q && k[id[t]] <= sum+a[i]-pre-1) {
            ans[id[t]] = k[id[t]]-sum+pre;
            t++;
        }
        // 値の更新
        sum += a[i]-pre-1;
        pre = a[i];
    }
    for (int i = t; i < q; i++) ans[id[i]] = k[id[i]]-sum+pre;
    for (int i = 0; i < q; i++) cout << ans[i] << endl;
    return 0;
}

感想