ABC061C

バケツソートと呼ばれるタイプの問題らしい。

――――――――――――――――――――――――
問題文
空の配列が1つあります。
この配列に、整数を配列に挿入する操作をN回行います。
i(1≦i≦N)回目の操作では、配列に整数aiをbi個挿入します。
N回の挿入操作後の配列の中で、K番目に小さい数を求めてください。
例えば、配列が{1,2,2,3,3,3}の時、4番目に小さい数は3となります。
制約
• 1≦N≦10^5
• 1≦ai,bi≦10^5
• 1≦K≦b1…+…bn
• 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K
a1 b1
:
aN bN
出力
N回の挿入操作後の配列の中で、K番目に小さい数を出力せよ。
――――――――――――――――――――――――

考え方

ai、biが最大10^5なので、配列にaiをbi個入れる操作をしていては間に合わない。また、aとbの値を2次元配列に入れようとも思ったがソートでつまづく。
そのため、要素数10^5の配列を1つ作り、配列のai番目の要素にbiを足していくという方法をとる(配列の添え字がaiに、要素がbiに対応する)。この方法を使うと、ai=ajとなったりしてもvec[ai] = bi+bjになるし、最終的に小さいほうからK番目を数えるときにも、配列を順番に見ていくだけで数えられる。

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

int main() {
 long n,k;
 cin >> n >> k;

 vector<long> vec(100001);
 for(int i=0; i<n; i++){
   int a,b;
   cin >> a >> b;
   vec[a] += b;
 }
 long cnt = 0;
 int ans;
 for(int i=0; i<100002; i++){
   cnt += vec[i];
   if(cnt >= k){
     ans = i;
     break;
   }
 }
 cout << ans << endl;
}

ぼーっとしてたらC++で解いてました。