ABC061 C問題（Big Array）を解く

AtCoder が提供しているABC（AtCoder Beginner Contest）061 C問題をC++で解いてみました。ABC061は、2017年5月13日21:00に実施されました。

AtCoder の紹介はこちらに、プログラミングの方針はこちらに記事があります。

C問題 Big Array（Difficulty : 808）

問題の詳細は、リンク先をご覧ください。

ABC061 C問題 Big Array

配列に挿入した数をまとめて計算します。AtCoder Problems による Difficulty は 808 でした。

解答案

C++ プログラム例（ABC061C）

C++ の map コンテナは順序付きです。このため、ある数字の個数を map コンテナに記憶して、$K$ 個目の数を求めます。

$K$ は、32ビット整数に収まらないことがあるため64ビット整数にしています。

以下が、C++プログラムです。

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

typedef long long int ll;

int main()
{
	int n;
	ll k;
	cin >> n >> k;
	map<int, ll> m;
	for (int i = 0; i < n; ++i) {
		int a;
		ll b;
		cin >> a >> b;
		m[a] += b;
	}

	ll sum = 0;
	for (auto e : m) {
		if (k <= sum + e.second) {
			cout << e.first << endl;
			break;
		}
		sum += e.second;
	}

	return 0;
}

AC（Accepted＝正しいプログラム）と判定されました。

最後に

この当時は、この問題も緑レートの問題でした。

引き続き ABC の問題を紹介していきます。