【題解】Zerojudge c067 - 00591 - Box of Bricks

題目連結

題目大意

給定 $n$ 堆積木，每次操作可以選擇將一堆的一個積木搬到另外一堆。求讓每堆積木數量相同的最少操作次數。

題解

因為每堆方塊的高度都要相同，不難想到最後的高度就是 $Average = \frac{\text{方塊總數}}{n}$，也就是方塊高度的平均值。需要注意的地方是我們是要計算操作的次數，因此答案為 $\frac{\sum\limits_{i = 0}^{n - 1} |Average - a_i|}{2}$，除以 $2$ 是因為一次操作我們將某個方塊從一堆移動到另外一堆，一次改變兩堆的數值。其他實作的細節請參考 code。

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	int id = 1;
	while(cin >> n && n) {
		cout << "Set #" << id++ << "\n";
		vector<int> a(n);
		for(int i = 0; i < n; i++) {
			cin >> a[i];
		}
		int average = accumulate(a.begin(), a.end(), 0) / n;
		int ans = 0;
		for(int i = 0; i < n; i++) {
			ans += abs(average - a[i]);
		}
		ans /= 2;
		cout << "The minimum number of moves is " << ans << ".\n";
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge c067 - 00591 - Box of Bricks