Koios1143的筆記

UVa 591

發表於 分類於

UVa 591

題目

http://domen111.github.io/UVa-Easy-Viewer/?591

給一排疊得高高的積木群，現在我們要把他們得高度都變一樣，而每次我們可以將任意得一塊積木移動到另一排積木上

問最小移動次數，使得積木得高度能完全相同

想法

既然可以任意移動積木，那麼我們只需要關心高度高於平均值的積木堆，並將他們的積木平均給矮的積木堆

至於怎麼分給積木堆並不是我們關心的，所以我們只需要計算有哪些積木是需要移動的即可

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
using namespace std;
int arr[55];
int cnt,n,ans,Case=1;
int main(){
	while(cin>>n && n){
		cnt=0;
		ans=0;
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
			cnt+=arr[i];
		}
		cnt/=n;
		for(int i=0 ; i<n ; i++){
			if(arr[i]>cnt)
				ans+=(arr[i]-cnt);
		}
		cout<<"Set #"<<Case++<<"\n";
		cout<<"The minimum number of moves is "<<ans<<".\n\n";
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(n)$

找答案的時間複雜度為 $O(n)$

每筆測資總時間複雜度為 $O(2n)$ 約為 $O(n)$