ABC061: C - Big Array
問題
C: Big Array - AtCoder Beginner Contest 061 | AtCoder
解答
数を重複して配列に持つ事ができ、更に配列の順序は常にソートした状態で考えて良いため、
数を数え上げられて、かつ数の種類でソートされるデータ構造として、std::map
を考えれば良い。
std::map<int, int64_t> num;
として、各操作に対してnum[a] += b
を行う。
要素を先頭から舐めてK
の値をK -= num[a]
で減算していき、
K <= 0
となった時点で、その時使用したa
を出力すれば良い。
int main() { int N; ll K; cin >> N >> K; std::map<int, ll> mp; rep(i, N) { int a, b; cin >> a >> b; mp[a] += b; } for (auto iter = mp.begin(); iter != mp.end(); ++iter) { K -= mp[iter->first]; if (K <= 0) { std::cout << iter->first << "\n"; return 0; } } return 0; }