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;
}