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++で解いてました。