[AtCoder] [經典競程 90 題] 014 - We Used to Sing a Song Together(★3)

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_n
題目大意:
有 $N$ 個國小生要去上小學,並且剛好也有 $N$ 個小學。一個住在 $A_i$ 的國小生要去 $B_j$ 的國小的不方便度為 $|A_i - B_j|$ ,現在你要安排每個國小生要去的學校,使得所有國小生的總不方便度最低。注意在這題每個國小生都要去不同的小學。
對兩個數列排序對項絕對值差和就是答案,不過其實我好像不會證 @_@
#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n; cin >> n;
	vector<lld> a(n), b(n);
	for (lld &ai: a) cin >> ai;
	for (lld &bi: b) cin >> bi;
	sort(a.begin(), a.end());
	sort(b.begin(), b.end());
	lld ans = 0;
	for (int i = 0; i < n; ++i)
		ans += abs(a[i] - b[i]);
	cout << ans << '\n';
	return 0;
} 

留言

這個網誌中的熱門文章

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

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

[Codeforces] 731D. 80-th Level Archeology