# 演算法課程題解 - 陣列

# UVa 591
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?591
給一排疊得高高的積木群，現在我們要把他們得高度都變一樣，而每次我們可以將任意得一塊積木移動到另一排積木上
問最小移動次數，使得積木得高度能完全相同

## 解法 By Koios1143
### 想法
既然可以任意移動積木，那麼我們只需要關心高度高於平均值的積木堆，並將他們的積木平均給矮的積木堆
至於怎麼分給積木堆並不是我們關心的，所以我們只需要計算有哪些積木是需要移動的即可

### 程式碼

#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)$

# UVa 10963
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10963
再東西向上有一群南北向的裂縫，對於每群裂縫我們可以把他們南北向任意移動
當所有裂縫的高度都相同時，裂縫就不存在了
現在給你每個裂縫的 $(y_1,y_2)$ ，求是否可以將裂縫補齊

## 解法 By Koios1143
### 想法
題目的意思其實就是因為可以任意移動，只要所有的裂縫高度都相同，那裂縫就能補齊
那麼我們只需要判斷是不是所有的高度都相同即可

拿一個變數去紀錄有出現過的高度，當有裂縫的高度跟他不同時，答案就會是 `no` ，所有高度都相同時為 `yes`

### 程式碼

#include<iostream>
#include<cmath>
using namespace std;
int n,m;
int main(){
	cin>>n;
	bool out=false;
	while(n--){
		if(out) cout<<"\n";
		else out=true;
		cin>>m;
		int cnt=-1; // 紀錄高度
		bool done=true;
		for(int i=0,x,y ; i<m ; i++){
			cin>>x>>y;
			if(cnt==-1) cnt=abs(x-y);
			else if(cnt!=abs(x-y))
				done=false;
		}
		if(done)
			cout<<"yes\n";
		else
			cout<<"no\n";
	}
	return 0;
}

### 時間複雜度分析
每筆測資輸入與計算高度時間複雜度為 $O(m)$
每筆測資總時間複雜度為 $O(m)$

# UVa 11059
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11059
給一個序列，問最大連續元素的乘積

## 解法 By Koios1143
### 想法
因為這題的 $N$ 很小，所以可以直接暴力做
枚舉開頭跟結尾，將其中的元素乘起來，並找出最大值

注意乘積可以到 $10^{18}$ ，記得開 long long

### 程式碼

#include<iostream>
using namespace std;
int n,arr[20],Case=1;
long long ans,tmp;
int main(){
	while(cin>>n){
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		ans=0;
		for(int i=0 ; i<n ; i++){
			// i 表示開頭
			tmp=1;
			for(int j=i ; j<n ; j++){
				// j 表示結尾
				tmp*=arr[j];
				ans=max(ans,tmp);
			}
		}
		cout<<"Case #"<<Case++<<": The maximum product is "<<ans<<".\n\n"; 
	}
	return 0;
}

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(n)$
枚舉答案的時間複雜度為 $O(n^2)$
每筆測資總時間複雜度為 $O(n+n^2)$ 約為 $O(n^2)$

# ZJ b840
## 題目
https://zerojudge.tw/ShowProblem?problemid=b840
給一個 $n \times n$ 的陣列，求最大矩形和

## 解法 By Koios1143
### 想法
暴力枚舉左上角的點以及長寬，將答案加總後取最大值
因為本題題目範圍很小可以這樣做

### 程式碼

//By Koios1143
#include<iostream>
using namespace std;
int n,arr[25][25],ans=0,cnt=0;
int main(){
	cin>>n;
	for(int i=0 ; i<n ; i++){
		for(int j=0 ; j<n ; j++){
			cin>>arr[i][j];
		}
	}
	for(int i=0 ; i<n ; i++){
		for(int j=0 ; j<n ; j++){
			for(int k=0 ; k+i<n ; k++){
				for(int l=0 ; l+j<n ; l++){
					cnt=0;
					for(int p=i ; p<=i+k ; p++){
						for(int q=j ; q<=j+l ; q++){
							cnt+=arr[p][q];
						}
					}
					ans=max(cnt, ans);
				}
			}
		}
	}
	cout<<ans<<"\n";
	return 0;
}

### 複雜度分析
總時間複雜度為 $O(n^2 + n^6)$

###### tags: `SCIST 演算法 題解`