「k 番目を求める」に関する典型的な処理を要求される問題。

問題概要

空集合 $S$ に対して、以下の $N$ 回の操作を行う:

$S$ に整数 $a_i$ を $b_i$ 個挿入する

$N$ 回の操作後の S において $K$ 番目に小さな値を求めよ。

制約

$1 \le N, a_{i}, b_{i} \le 10^{5}$

考えたこと

この問題の注意点として、 $S$ を具体的に作ろうとすると、最大で $10^{10}$ くらいのサイズになってメモリも計算時間も飛んでしまうので注意。。。

さて、「 $K$ 番目の値を求めなさい」というタイプの問題で考えることは、

整数 x 以下の要素が $K$ 個以上あるような最小の x を求める

という風に考えると考えやすいことが多い。そしてそのパターンは

x を小さい方から見ていって、x 以下の整数が $K$ 個以上になるまで $x$ を増やしていく
二分探索する
その他色々

という感じ。二分探索するケースはあまりにも多いけど、今回はそこまで考えなくても素直に一番上の方法で解くことができる。すなわち

$(a_i, b_i)$ を $a_i$ が小さい順にソートする
$a_i$ が小さい順に $b_i$ を合計していって、はじめて $K$ 以上になった時点での $a_i$ が答えである

という感じ。実装上は ( $a_i, b_i$ ) をペアとしたベクトルを作って、ペアとしてソートを行うと良い。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int N; long long K;
    cin >> N >> K;
    vector<pair<long long, long long> > v(N);
    for (int i = 0; i < N; ++i) cin >> v[i].first >> v[i].second;

    // ソート
    sort(v.begin(), v.end());
    
    // a_i が小さい順に b_i を合計して K 以上になる瞬間をとらえる
    long long res = 0;
    long long sum = 0;
    for (int i = 0; i < N; ++i) {
        sum += v[i].second;
        if (sum >= K) {
            res = v[i].first; // sum >= K になった瞬間の a_i
            break;
        }
    }
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 061 C - Big Array (緑色, 300 点)

問題概要

制約

考えたこと