# 演算法課程題解 - 分治法

# UVa 839
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?839


我們都知道秤子有力矩，如果要讓秤子維持平衡的狀態，則左右兩側的力矩必須要相同
現在有很多秤子互相連接再一起，如下圖

告訴你每個天平的 `左力矩(Dl)` `右力矩(Dr)` `左物重(Wl)` `右物重(Wr)`
如果 Dl 或是 Dr 為 0 則表示在左側或是右側接的是秤子，接下來會依序告訴你左側或是右側的秤子狀態

問全部的天秤是不是都能維持平衡的狀態

## 想法 By Koios
一個天平要是平衡的，就必須要讓 `左總物重*左力臂` = `右總物重*右力臂`
輸入會依照由上而下、由左而右的順序輸入進來，所以我們可以用遞迴的方式找出每個子秤子的重量，再來判斷秤子的左右是否平衡

### 程式碼

//By Koios1143
#include<iostream>
using namespace std;
int t;
bool ans;

int solve(){
	int Wl, Dl, Wr, Dr;
	cin>>Wl>>Dl>>Wr>>Dr;
	// 先找出子秤子的重量
	if(Wl == 0){
		Wl = solve();
	}
	if(Wr == 0){
		Wr = solve();
	}
	// 再判斷是否平衡
	if(Wl*Dl != Wr*Dr){
		ans = false;
	}
	// 將當前秤子的總重量回傳
	return Wl + Wr;
}

int main(){
	cin>>t;
	for(int i=0 ; i<t ; i++){
		ans = true;
		if(i) cout<<"\n";
		solve();
		if(ans){
			cout<<"YES\n";
		}
		else{
			cout<<"NO\n";
		}
	}
	return 0;
}

# UVa 10810
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10810

經典問題，逆序數對
給一串序列，問 bubble sort 由小到大排序需要交換幾次

## 想法 By Koios
要問 bubble sort 的交換次數，等同在問 序列中有多少組 $i, j \quad i<j$ 使得 $a_i > a_j$，也就是所謂的逆序數對
因為唯有前面比較大的數字必定會和後面比較小的數字交換

試著把序列切一半，會發現問題變成問
1. 在左半邊的逆序數對
2. 在右半邊的逆序數對
3. 橫跨左右兩側的逆序數對

如此一來，左側、右側也可以看做是新的子問題，等同分別在問左側及右側這兩個序列的逆序數對量，那麼我們就可以把問題切割下去遞迴求解
至於橫跨左右兩側的就在合併的時候處理

這樣的架構跟 merge sort 其實是類似的
如果就跟著 merge sort 的架構走，會發生什麼事呢?

當我要合併兩區域時，兩側的序列都是已經由小到大排序好的
那麼當我要找有多少組逆序數對時，我們就只需要去看 **右側的元素是否小於左側**
如果是，那麼右側元素也必定會小於左側剩餘的所有元素，反過來說，這些就是我們要找的逆序數對

因此，整個問題變成，在序列 merge sort 合併過程當中，右側元素小於左側元素時，左側元素剩餘數量總合為多少

### 程式碼

//By Koios1143
#include<iostream>
using namespace std;
int n, arr[500010], tmp[500010];
long long ans;

void merge(int L, int R){
	int mid = (L+R)>>1;
	for(int i=L, j=mid+1, k=L ; k<=R ; k++){
		if(i>mid){
			tmp[k] = arr[j++];
		}
		else if(j>R){
			tmp[k] = arr[i++];
		}
		else if(arr[i] > arr[j]){
			// 當右側元素較小，則左側剩餘所有元素都可與 j 形成逆序數對
			ans += mid+1-i;
			tmp[k] = arr[j++]; 
		}
		else{
			tmp[k] = arr[i++];
		}
	}
	for(int i=L ; i<=R ; i++){
		arr[i] = tmp[i];
	}
}

// [L, R]
void mergesort(int L, int R){
	if(L == R) return;
	int mid = (L+R)>>1;
	mergesort(L, mid);
	mergesort(mid+1, R);
	merge(L, R);
}

int main(){
	while(cin>>n && n){
		ans = 0;
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		mergesort(0, n-1);
		cout<<ans<<"\n";
	}
	return 0;
}

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(n)$
每筆測資尋找逆序數對時間複雜度為 $O(nlogn)$
每筆測資總時間複雜度為 $O(n + nlogn)$

# UVa10602
*待檢查*
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10602

輸入一系列的單字，求輸入字母最少的次數，第一個字串需要最早輸出。

## 想法:
先排序字串再尋找有最長相同前綴的單字
這樣就可以減少輸入次數
之後可以用暴力解(但很麻煩，也可以儲存開表格檢查

# TOJ 472
## 題目
https://toj.tfcis.org/oj/pro/472/

給一個長度 $N$ 的序列， $3 \leq N \leq 10^{6}$
定義一組順序數對有三個數字 $a_i, a_j, a_k$，並且滿足 $i < j < k$ 且 $a_i < a_j < a_k$
求序列當中有多少組順序數對

## 想法 By Koios
比 $a_j$ 還小並且在它左邊的數字的數字乘上比 $a_j$ 還大並且在它右邊的數字就會是以 $a_j$ 為順序數對中間值的數對組數
對於每個數字都找出這兩種數值相乘，其總和就會是答案

要找出有多少在自己右邊並且比自己大的數字可以用 merge sort 由小到大排序來找到
在合併跨兩邊的序列過程當中，可以保證右邊的序列都在自己的右邊
如果在右邊的序列中找到一個比當前左邊元素還大的，那麼右邊剩餘的所有元素都比自己大

找出每個數字有多少在自己右邊右比自己大的數字之後，接下來要找在自己左邊並且比自己小的數字
這同樣可以用 merge sort 找到，不過是由大到小排序
在合併跨兩邊的序列過程當中，可以保證左邊的序列都在自己的左邊
如果在左邊的序列中找到一個比當前右邊元素還小的，那麼左邊剩下的所有元素都比自己大

### 程式碼

//By Koios1143
#include<iostream>
using namespace std;
long long n, m, ans=0, bigger[1000005];
pair<long long ,int> arr[1000005], ary[1000005], tmp[1000005];

// 由小到大排序
// 對 ary 序列排序，放在 tmp 序列中
void merge_sort(int L, int R){
    if(L==R) return;
    int mid = (L+R)>>1;
    merge_sort(L, mid);
    merge_sort(mid+1, R);
    for(int i=L, j=mid+1, k=L ; k<=R ; k++){
        if(i > mid){
            tmp[k] = ary[j++];
        }
        else if(j > R){
            tmp[k] = ary[i++];
        }
        else if(ary[i].first < ary[j].first){
	// 找到比 ary[i] 還大，並且在右側的元素
            bigger[ary[i].second] += R-j+1;
            tmp[k] = ary[i++];
        }
        else{
            tmp[k] = ary[j++];
        }
    }
    for(int i=L ; i<=R ; i++){
        ary[i] = tmp[i];
    }
}

// 由大到小排序
// 對 arr 排序排序，放在 tmp 序列中
void merge_sort2(int L, int R){
	if(L == R) return;
	int mid = (L+R)>>1;
	merge_sort2(L, mid);
	merge_sort2(mid+1, R);
	for(int i=L, j=mid+1, k=L ; k<=R ; k++){
		if(i>mid){
			tmp[k] = arr[j++];
		}
		else if(j > R){
			tmp[k] = arr[i++];
		}
		else if(arr[i].first < arr[j].first){
			// 找到比 arr[j] 還小，並且在左側的元素
			// 乘上比 arr[j] 還大的元素數量就找到了順序數對
			ans += (mid-i+1)*bigger[arr[j].second];
			tmp[k] = arr[j++];
		}
		else{
			tmp[k] = arr[i++];
		}
	}
	for(int i=L ; i<=R ; i++){
		arr[i] = tmp[i];
	}
}

int main(){
    cin>>n;
    for(int i=0 ; i<n ; i++){
        cin>>m;
        arr[i] = make_pair(m, i);
        ary[i] = arr[i];
        bigger[i] = 0;
    }
    merge_sort(0, n-1);
    merge_sort2(0, n-1);
    cout<<ans<<"\n";
    return 0;
}

### 時間複雜度分析
輸入時間複雜度為 $O(n)$
找答案時間複雜度為 $O(nlogn)$
總時間複雜度為 $O(n + nlogn)$

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