[AtCoder] [經典競程 90 題] 007 - CP Classes(★3)

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_g
題目大意:
給定$N$個數字 $A_i$ ,對於 $Q$ 比詢問的每個 $B_i$,請找到 $\min_j |A_j - B_i|$ 。
直接拿個平衡樹 (例如 C++ STL 內建的 std::set) 查一下就做完ㄌ。
#include <bits/stdc++.h>
using namespace std;
constexpr int INF = 1 << 30;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	set<int> s;
	for (int i = 0; i < n; ++i) {
		int x; cin >> x;
		s.insert(x);
	}
	int q; cin >> q;
	while (q--) {
		int x; cin >> x;
		auto it = s.lower_bound(x);
		int ans = INF;
		if (it != s.end()) ans = min(ans, *it - x);
		if (it != s.begin()) ans = min(ans, x - *prev(it));
		cout << ans << '\n';
	}
	return 0;
} 

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology