ABC 61 C

問題概要

  • 空の配列が１つあ理、この配列に整数を挿入する操作を\(N\)回行う。
  • \(i(1 ≤ i ≤ N)\)回目の操作では、配列に整数\(a_i\)を\(b_i\)個挿入する。
  • \(N\)回の挿入操作後の配列の中で\(K\)番目に小さい数を求めよ。

制約

  • \(1 ≤ N ≤ \)105
  • \(1 ≤ a_i, b_i ≤ \) 105
  • \(1 ≤ K ≤ b_1 ... + ... b_n\)

考えたこと

  • \(a_i\)が昇順に入力されるとは限らないので昇順に並び替えてあげる必要がある。
  • \(a_i\) がそれほど大きくないため、どの数字が何個出現したかを表現する配列を用意する( バケツソート )
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int AMAX=100000;
ll cnt[AMAX+1];

int main() {
  ll n, k; cin >> n >> k;
  for(ll i = 0; i < n; ++i) {
    ll a, b; cin >> a >> b;
    cnt[a] += b;
  }
  
  for(ll ans = 1; ans <= AMAX; ++ans) {
    if(k <= cnt[ans]) {
      cout << ans << endl;
      break;
    }
    k -= cnt[ans];
  }

  return 0;
}