c067 - 00591 - Box of Bricks
題目描述
題目描述了小明有幾堆不同高度的積木，他希望通過搬動最少數量的積木，使得所有堆積的高度相同。輸入包含多組測試案例，每組案例包含堆數和每堆的高度。輸出每組案例需要搬動的最小積木數量。
解題思路
解題思路是首先計算所有積木高度的平均值。然後，計算每堆積木與平均值之間的差的絕對值，並將這些差的絕對值加總。最後，將加總結果除以 2，即可得到最小搬動次數。這是因為每次搬動可以將一個積木從高處移到低處，或者從低處移到高處，所以總的搬動次數是差的絕對值之和的一半。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int main(){
int a=0,b=0,c=1,sum=0;
while(cin >> a){
if(a>0){
int d[a];
for(int i=0;i<a;i++){
cin >> d[i];
b+=d[i];
}
b/=a;
for(int i=0;i<a;i++){
if(d[i]-b<0){
sum+=(d[i]-b)*(-1);
}
else{
sum+=(d[i]-b);
}
}
cout << "Set #" << c << endl;
cout << "The minimum number of moves is " << sum/2 << "." << endl;
cout << endl;
sum=0;
a=0;
b=0;
c++;
}
}
}