007.md

007 - CP Classes (★3)

解答

#include <iostream>
#include <vector>
#include <algorithm> // std::sort(), std::lower_bound(), std::distance(), std::max(), std::min()

int main()
{
	// N 個のクラス
	int N;
	std::cin >> N;

	// 対象レーティング
	std::vector<int> A(N);
	for (auto& a : A)
	{
		std::cin >> a;
	}
	// 小さい順にソート
	std::sort(A.begin(), A.end());

	// Q 人の入塾
	int Q;
	std::cin >> Q;

	for (int i = 0; i < Q; ++i)
	{
		// 入塾者のレーティング
		int b;
		std::cin >> b;

		// b 以上の値が現れる手前の位置のイテレータを取得
		const auto it = std::lower_bound(A.begin(), A.end(), b);

		// 先頭イテレータから it までの距離
		const int pos = static_cast<int>(std::distance(A.begin(), it));

		// 候補のクラスのインデックス 1
		const int c1 = std::max(0, pos - 1);

		// 候補のクラスのインデックス 2
		const int c2 = std::min(pos, N - 1);

		// 候補のクラス 1 のコスト
		const int c1Cost = std::abs(A[c1] - b);

		// 候補のクラス 2 のコスト
		const int c2Cost = std::abs(A[c2] - b);

		// 小さいほうを解答として出力
		std::cout << std::min(c1Cost, c2Cost) << '\n';
	}
}