# 演算法課程題解 - 貪心法

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

林希是個購物狂，每次只要有買二送一的活動都會參加，身為她的朋友，你想幫她盡可能地省下最多的錢

假如一次購物的商品價值分別有 $400, 350, 300, 250, 200, 150, 100$，如果一次結帳只會省下最便宜的兩個商品 $100 + 150 = 250$ 元
但是如果分開三次結帳 $400, 350, 300$ / $250, 200, 150$ / $100$ 則可以省下 $300 + 150 = 450$ 元

請問給你購物商品的價格，可以隨意分開結帳的情況下，最多可以省下多少錢

## 想法 By Koios
既然每次送的都是結帳中最便宜的商品，那麼我們想要省最多錢，就要盡可能地把價格最高的三項一起付，就可以省下第三高的價格

**證明**
假如我們有 $6$ 項商品，價格分別為 $a, b, c, d, e, f$，並且 $a \leq b \leq c \leq d \leq e \leq f$
如果分開結帳不採取上述策略，例如 $f, e, c$ / $d, b, a$ 則省下的錢為 $a + c$
必定會比 $f, e, d$ / $c, b, a$ 省下的 $d + a$ 還差，最好也是相同

---

由此可知，我們只需要將價格排序，每三個一組，把價格第三高的加起來，總和即為答案

### 程式碼

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int t, n, ans, arr[20010];
int main(){
	cin>>t;
	while(t--){
		ans=0;
		cin>>n;
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		// 由大到小排序
		sort(arr, arr+n, greater<int>());
		for(int i=2 ; i<n ; i+=3){
			ans+=arr[i];
		}
		cout<<ans<<"\n";
	}
	return 0;
}

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

客運公司中有 $n$ 位司機，同時有 $n$ 條公車路線
每位司機都會被分配到早上以及晚上各一條路線
如果當天司機駕駛的總距離超過 $d$ ，那麼每超過 $1$ 個單位距離，雇主就需要多付 $r$ 元的額外費用

現在告訴你 $n, d, r$ 以及每條路線在早上以及晚上路線長度分別為多長，求雇主的最小花費為何

## 想法 By Koios
無論如何，白天總長度最長的路線一定會有司機負責，如果晚上還給他較長的路線，如果超出 $d$ 則所需要付出的額外費用也必定更高
所以我們就索性把早上走最長的晚上走最短; 早上走第二長的晚上走第二短，以此類推

### 程式碼

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, d, r, ans, morning[105], night[105];
int main(){
	while(cin>>n>>d>>r && (n!=0 || d!=0 || r!=0)){
		ans = 0;
		for(int i=0 ; i<n ; i++){
			cin>>morning[i];
		}
		for(int i=0 ; i<n ; i++){
			cin>>night[i];
		}
		sort(morning, morning+n, greater<int>());
		sort(night, night+n);
		for(int i=0, tot ; i<n ; i++){
			tot = morning[i] + night[i];
			if(tot > d){
				ans += (tot-d)*r;
			}
		}
		cout<<ans<<"\n";
	}
	return 0;
}

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

有一個 $1 \times N$ 的田地，田地上有部分是無法種植作物的
在這個田地附近有很多烏鴉，為了避免烏鴉來吃掉作物，我們希望在田地上放幾個稻草人

稻草人可以保護的範圍包含了鄰近的左右兩個格子，並且可以插在田地上的任何一處
請問最少需要多少稻草人才能使所有可種植的地都能保護到

## 想法 By Koios
既然每塊可耕種田地都需要被覆蓋到，那麼每塊可耕種田地旁邊一定都有稻草人
並且可以保證，稻草人盡量往後插一定比較好
也就是說，當遇到像是 `...` 這種情況， `.*.` 一定比 `*..` 好
放在後面才可以有機會同時讓下一個田地也被保護到

### 程式碼

//By Koios1143
#include<iostream>
using namespace std;
int t, n, ans, cnt[105];
char arr[105];
int main(){
	cin>>t;
	for(int Case=1 ; Case<=t ; Case++){
		for(int i=0 ; i<105 ; i++){
			cnt[i] = 0;
		}
		ans=0;
		cin>>n;
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		for(int i=1 ; i<n ; i++){
			if(arr[i-1] == '.'){
				// 只在發現前一塊是好的田地才放稻草人
				arr[i-1] = '*';
				arr[i] = '*';
				arr[i+1] = '*';
				ans++;
			}
		}
		// 最後可能會有遺落，必定只會在最後面出現
		if(arr[n-1] == '.') ans++;
		cout<<"Case "<<Case<<": "<<ans<<"\n";
	}
	return 0;
}

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

有一個城堡受到龍的襲擊，這頭龍有 $N$ 個頭，並且需要將全部的頭都砍下才能打倒牠
每個直徑為 $x$ 的頭需要身高 $\geq x$ 的騎士才能砍下，並且每個騎士都至多只能砍一顆頭
而國王需要支付騎士的價格與該騎士的身高相同
現在告訴你這 $N$ 個龍頭的直徑以及 $M$ 個騎士的身高，問是否有可以擊退這頭龍
如果可以，請問國王至少要支付多少費用

## 想法
如果我們要付最少的錢，也就是希望騎士身高的總和要是最小
如果說要砍下龍頭，身高至少要比其直徑還大
那麼對於每個龍頭，我們都找最小可以砍下它的騎士就可以了

所以我們可以將龍頭、騎士身高皆由小到大排序
接下來從最小的龍頭開始，每次都找剛好可以砍下它的騎士，最終就可以找到答案

### 程式碼

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, m, ans, cnt, head[20010], knight[20010];
int main(){
	while(cin>>n>>m && (n!=0 || m!=0)){
		ans=0, cnt=0;
		for(int i=0 ; i<n ; i++){
			cin>>head[i];
		}
		for(int i=0 ; i<m ; i++){
			cin>>knight[i];
		}
		// 如果騎士數量比龍頭數量還小，必定不能擊敗
		if(n>m){
			cout<<"Loowater is doomed!\n";
			continue;
		}
		sort(head, head+n);
		sort(knight, knight+m);
		for(int i=0, j=0 ; i<n && j<m && cnt!=n ; ){
			if(knight[j] >= head[i]){
				ans += knight[j];
				i++, j++, cnt++;
			}
			else{
				j++;
			}
		}
		if(cnt != n){
			cout<<"Loowater is doomed!\n";
		}
		else{
			cout<<ans<<"\n";
		}
	}
	return 0;
}

### 時間複雜度分析
每筆測資輸入時間複雜度為 $O(n + m)$
每筆測資排序時間複雜度為 $O(nlogn + mlogm)$
每筆測資找答案時間複雜度為 $O(n + m)$
每筆測資總時間複雜度為 $O(n + m + nlogn + mlogm)$

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

有多筆測資，每筆測資包含一個正整數 $N$ ，請輸出一個最小的正整數 $Q$，使得 $Q$ 的每個數字相乘等於 $N$

## 想法 By Koios
因為數字是十進位的，所以我們只能使用 $0$~$9$ 這幾個數字

然而因為 $0$ 和所有數字相乘都會是 $0$，因此除了 $N=0$ 以外我們絕不會考慮 $0$
另外，因為 $1$ 和所有數字相乘都還是不變，除了 $N=1$ 的情況以外選擇放入 $1$ 只會讓數字 $Q$ 更大，因此絕不考慮使用

那麼接下來因為要讓乘積為 $N$ ，所以我們可以找出 $2$~$9$ 當中的每個數字各需要幾個才能使乘積為 $N$
但是要特別注意的是，我們**只能從 $9$ 開始往下找**
考慮 $N$ 同時是 $2$ 和 $4$ 的倍數的情況，那麼選擇 $2$ 只會讓我們多一個位數，讓 $Q$ 的結果更糟，$3$ 和 $9$ 也是同理

那麼，我們只需要從 $9$ 開始往下找是不是 $N$ 的因數，再返著從 $2$~$9$ 把找到的因數輸出即可

如此一來就可以保整乘積為 $N$ 的同時又會是最小值

### 程式碼

//By Koios1143
#include<iostream>
using namespace std;
int t, n, cnt[10];

int main(){
	cin>>t;
	while(t--){
		for(int i=0 ; i<=9 ; i++){
			cnt[i] = 0;
		}
		cin>>n;
		if(n == 0 || n == 1){
			cout<<n<<"\n";
		}
		else{
			// 先找出 9~2 每個數字需要多少個
			for(int i=9 ; i>1 ; i--){
				while(n%i == 0){
					cnt[i]++;
					n/=i;
				}
			}
			// 判斷 $n$ 能不能被整除
			if(n!=1){
				cout<<"-1\n";
			}
			else{
				// 反著輸出
				for(int i=2 ; i<=9 ; i++){
					while(cnt[i]--){
						cout<<i;
					}
				}
				cout<<"\n";
			}
		}
	}
	return 0;
}

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

在一個加油站他們會用數字牌來標示今天的汽油價格
然而為了物盡其用，我們可以將 $2$ 倒過來變成 $5$ ; $6$ 倒過來變成 $9$，反之亦然
現在我們已經標示了一個價格，請問在只能使用這些數字牌的情況下，你只能透過 **交換兩字牌** 或是 **旋轉某字牌** 來獲得新的數字
請問所有可以得到的新數字當中，比原本數字還大的最小值為何?
如果不能得到任何這樣的數字，請輸出 `The price cannot be raised.`

**範例說明**
輸入: `65.2`

可以直接將最後的 `2` 旋轉成 `5` 就是答案 `65.5`

## 想法 By Koios
既然要得到的是比原本大的數字中的最小值，那麼首先我們必須要比原數字大
為了要讓結果最小化，我們希望越低位的數字被變大越好

於是我們可以從最低位開始往高位看，記錄下到目前為止我們可以使用的數字有哪些，包含了**交換**以及**旋轉**
只要記錄的數字當中有比當前關注的數字來的大，那就交換過來

例如說 `64.7` 在 `4` 這個位置上我們可以用的數字包含了 `4` `7`，發現到 $7 > 4$ 就交換過來變成 `67.4`

交換過一次之後我們就獲得比原本來的大的數字了，並且我們只修改了可修改數字中的最低位
接下來我們就只需要讓它是最小值

假設剛才交換的位置是 $i$
要讓它是最小值，我們就必須要讓第 $i$ 位以下的數字盡量小
那麼就乾脆把第 $i$ 位以下的數字由小到大放進去即可

例如 `124421`，經過第一個步驟會先變成 `142421` ，第二步會將第 $5$ 位數 $4$ 以下的所有數字由小到大排入變成 `141224`

### 程式碼

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
string n;
int start, cnt, vis[10];
char tmp[35];

int main(){
	while(cin>>n && n!="."){
		// 初始化
		for(int i=0 ; i<10 ; i++){
			vis[i] = -1;
		}
		
		// 先變大
		// 記得 vis 存的只能是第一次找到的位置，才能保證最佳
		start = 0;
		for(int i=n.size()-1 ; i>=0 && start == 0 ; i--){
			if(n[i] == '.') continue;
			if(n[i] == '2' || n[i] == '5'){
				if(vis[2] == -1){
					vis[2] = i;
				}
				if(vis[5] == -1){
					vis[5] = i;
				}
			}
			else if(n[i] == '6' || n[i] == '9'){
				if(vis[6] == -1){
					vis[6] = i;
				}
				if(vis[9] == -1){
					vis[9] = i;
				}
			}
			else if(n[i] != '.'){
				if(vis[n[i]-'0'] == -1){
					vis[n[i]-'0'] = i;
				}
			}
			
			for(int j=n[i]-'0'+1 ; j<10 ; j++){
				if(vis[j] != -1){
					if(vis[j] == n[i]){
						n[i] = '0' + j;
					}
					else{
						n[vis[j]] = n[i];
						n[i] = '0'+j;	
					}
					start = i+1;
					break;
				}
			}
		}
		
		// 無法變大就找不到答案
		if(start == 0){
			cout<<"The price cannot be raised.\n";
			continue;
		}
		
		// 找到最小值
		cnt=0;
		for(int i=start ; i<n.size() ; i++){
			if(n[i] == '9') tmp[cnt++] = '6';
			else if(n[i] == '5') tmp[cnt++] = '2';
			else if(n[i] != '.') tmp[cnt++] = n[i];
		}
		// 將數字由小到大放進去
		sort(tmp, tmp+cnt);
		for(int i=start, j=0 ; i<n.size() ; i++){
			if(n[i] != '.'){
				n[i] = tmp[j++];
			}
		}
		cout<<n<<"\n";
	}

	return 0;
}

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

有一隻青蛙要從池塘的左側跳掉右側，然後再跳回左側，途中只能透過石頭當作中繼站
石頭又分成兩種，大石頭(B)以及小石頭(S)
大石頭可以無限次使用，但是小石頭只能跳一次
問最短一次需要跳多遠才能達成

輸入的石頭會依照距離由小到大輸入

## 想法 By Koios
題目等價於有兩隻青蛙同時從左岸跳到右岸，但是兩隻青蛙不能同時在小石頭上

那麼首先，無論如何如果發現前面有大石頭，讓兩隻青蛙都跳上這個石頭必定會是最好的
如果不跳到大石頭上，則必定有一隻青蛙需要更大的跳躍力跳到下一個石頭上

那麼如果遇到的是小石頭，如果選擇兩隻青蛙都不跳過去，一定會讓兩隻青蛙需要更大的跳躍力
所以我們必定會選擇一隻青蛙跳上去

所以說每個石頭都會有至少一隻青蛙走過

我們可以先讓兩隻青蛙都在起點 ($x=0$) 的位置上
接下來看距離兩隻青蛙最近的石頭是 B 還是 S
1. 如果是 B ，兩隻青蛙都跳上去
2. 如果是 S ，選擇一隻當前距離終點最遠的青蛙跳上去

就這樣把每個石頭都看過一次就可以找到最大的移動距離了

### 程式碼

//By Koios1143
#include<iostream> 
using namespace std;
int cntS, cntB, T, N, D, M, ans, p, q, S[105], B[105];
char c, tmp;

int main(){
	cin>>T;
	for(int Case=1 ; Case<=T ; Case++){
		cntS = cntB = ans = p = q = 0;
		cin>>N>>D;
		// 先將 B 和 S 石頭的位置記錄下來
		for(int i=0 ; i<N ; i++){
			cin>>c>>tmp>>M;
			if(c == 'B'){
				B[cntB++] = M;
			}
			else{
				S[cntS++] = M;
			}
		}
		
		for(int i=0, j=0 ; i<cntB || j<cntS ; ){
			// 如果 S 石頭已經用完了
			// 或是 B 石頭還有，並且距離比 S 石頭還近
			// 那就讓兩隻青蛙都跳到 B
			if(j >= cntS || (i<cntB && B[i] <= S[j])){
				ans = max(ans, B[i]-p);
				ans = max(ans, B[i]-q);
				p = q = B[i];
				i++;
			}
			else{
				// 否則選擇一個距離終點較遠的青蛙跳到 S
				if(p < q){
					// 選擇 p
					ans = max(ans, S[j]-p);
					p = S[j];
					j++;
				}
				else{
					// 選擇 q
					ans = max(ans, S[j]-q);
					q = S[j];
					j++;
				}
			}
		}
		// 最後別忘了還有終點
		ans = max(ans, D-p);
		ans = max(ans, D-q);
		cout<<"Case "<<Case<<": "<<ans<<"\n";
	}

	return 0;
}

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

有 $N$ 個正整數，你可以任意選擇數字串接的方式，請問串接起來的最大值為和

舉例來說， $N$ 個數字包含 $\{123, 124, 56, 90\}$
串接最大值就會是 $9056124123$

## 想法 By Koios
第一個想法是先把數字依照字典續由大到小排序，但是這樣的想法只在所有的數字長度都相同才符合

如果兩個數字長度不相同，並且沒有相同前綴，那麼直接找首位數字最大的排前面一定會是最好

但是如果兩個數字長度不相同，並且擁有相同的前綴，那麼應該要選誰放在前面比較好?
例如說 $1234, 123$，在這個例子當中 $1234123$ 會是最好
再舉例 $909, 99$，在這個例子當中 $99909$ 會是最好
所以並不是數字短就放前面，或是說數字長就放前面

這時候發現到，其實我們一直再找的不就是兩數字 $A, B$ 轉成字串後是 $AB$ 比較好還是 $BA$ 比較好嗎?
那麼何不直接將所有數字都以字串的形式排序，而排序方式則是判斷 $AB$ $BA$ 哪個會使字典序越大
如此一來我們的排序結果串接起來就會是所求

### 程式碼

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n;
string arr[55];

bool cmp(string a, string b){
	return a+b > b+a;
}

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

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

在 $x$ 軸上有一個長 $l$ 寬 $w$ 的長方形，長方形的左界在座標 $x=0$ 的位置上
同樣在 $x$ 軸上有許多個圓心在 $x_i$ ，半徑為 $r_i$ 的圓，你可以任意選取這些圓
請問你最少可以用多少的圓覆蓋整個長方形

## 想法 By Koios
因為是用圓來覆蓋長方形的面積，所以不能單純只考慮圓形的左界以及右界
力如下圖，兩個圓和長方形之間還有未覆蓋到的面積(青藍色部分)

不過我們可以利用畢氏定理找到新的左界跟右界

那麼這樣一來只要兩個圓的新左界跟新右界至少是相互碰在一起，就可以保證這兩個圓之間不會有像上面沒覆蓋到的面積了


那麼接下來我們就只需要找出這些新的左界以及新的右界，就可以直接忽略"圓"了
整個問題轉換成線段覆蓋問題!
可以想成把圓形變成長方形

轉換成了線段覆蓋問題，也就是說每次檢查可以覆蓋到當前左界的"長方形"當中，最遠可以覆蓋到哪裡，我們就拿它，可以保證使用最少的"長方形"

:::info
因為需要計算根號，記得使用 double 來進行計算
:::

### 程式碼

//By Koios1143
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int n, px, ans;
double l, w, x, r,range, best, best_px;
pair<double, double> arr[10005];

int main(){
	while(cin>>n>>l>>w){
		// 畢氏定理只需要寬的一半就好
		w /= 2;
		px = ans = 0;
		
		for(int i=0 ; i<n ; i++){
			cin>>x>>r;
			// 由於直角三角形斜邊必定大於另外兩邊，所以直接移除不形成直角三角形的情況
			if(r <= w) continue;
			range = sqrt(r*r - w*w);
			arr[px++] = make_pair(x-range, x+range);
		}
		sort(arr, arr+px);
		
		// 後面 x 表示當前的左界，初始從 0 開始
		x = 0;
		for(int i=0 ; i<px && x<l ; ){
			// 對於每個當前左界，找出所有所有在他左邊的圓，並且只取出最大右界
			best=-1, best_px=-1;
			while(arr[i].first <= x){
				if(arr[i].second > best){
					best = arr[i].second;
					best_px = i;
				}
				i++;
			}
			// 找不到就表示無解
			if(best == -1) break;
			else x = best, ans++;
		}
		// 最後檢查一下左界是否已經到達長方形的右界
		if(x < l) cout<<-1<<"\n";
		else cout<<ans<<"\n";
	}
	return 0;
}

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

在一個小鎮當中有一個小氣的木匠，他只願意用最少的螺絲做貨架，這導致了他的貨架十分脆弱
為了再使用這個貨架的時候能盡量避免壞掉，我們在擺放物品要盡量讓左右兩邊重量最重，且左右兩側的重量盡量平均分配

現在告訴你一個正整數 $N$， $N$ 介於 $1$~$26$ 之間，這表示我們需要關注的物品有哪些
接下來一行字串中只包含 $A$~$Z$ ，表示各種貨物，注意我們只需要關注 $N$ 種貨物，也就是 $A$~$(A+N-1)$，每個字母出現的次數就表示了他的重量

請問應該要怎麼擺放這些貨物才能盡量避免貨架損壞，如果存在多種排法，請輸出字典序最小的

## 想法 By Koios
沒錯，你只需要統計每個字母出現的次數，不過接下來就麻煩了
要平均分配重量的同時，又需要兼顧字典序最小，究竟要怎麼做?

想法是這樣
先考慮要平均分配重量，先不考慮字典序要最小
我們可以單純依照重量先排序好，然後接著兩個兩個拿，把兩個一個放前面一個放後面，慢慢放到中間
這樣就可以保證重量已經被盡量平均在兩側，而且越中間一定會越小

---

接下來要考慮字典序

也許你會想到，那我們就把剛剛分配完重量的結果重新看
每次看以中間為對稱軸的兩兩對稱物品，把字典序小的移動到前面
這樣兩側的重量分配仍然沒問題，而且也比剛剛的字典序好多了
例如

發現到 B 字典序比 A 大，交換會比原本好

但是很可惜的是，這樣的想法**並不全面**
因為剛剛並沒有考慮到字典序，所以可能會出現這種奇怪的情況

會被更新成

顯然不是最佳

---

**重新考慮新作法**
我們這次不一樣，在排序的過程當中也考慮字典序，讓他在數字相同的時候盡量讓字典序小的排在前方

像是這樣

這時候如果你嘗試手解，也許你會發現到一個解法
如果要放前面的時候，我就從這群**相同的數字裡面**找到還沒有放過的物品**字典序最小的**
如果要放後面的時候，我就從這群**相同的數字裡面**找到還沒有放過的物品**字典序最大的**
然後最後再把對稱的兩兩物品比較，把字典序小的放前面

例如上圖就會變成

這樣的想法就快接近正解了! 不過還需要考慮一種情況

實際上最好的解是這樣

也就是說，如果我要放前面的時候發現這個數字只剩下最後一個還沒用的了
那就必須要再看看下一個數字當中字典序最小的字母，字典序是不是也比自己小
如果是的話，就需要把它放在前面

### 程式碼

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int T, N, ans_num[26];
char c, ans_chr[26];
pair<int, char> arr[26];
bool used[26];

bool cmp(pair<int, char> a, pair<int, char> b){
	if(a.first != b.first) return a.first > b.first;
	else return a.second < b.second;
}

int main(){
	cin>>T;
	while(T--){
		for(int i=0 ; i<26 ; i++){
			arr[i].first = 0;
			arr[i].second = 'A'+i;
			used[i] = false;
		}
		
		cin>>N;
		while(cin>>c && c!='#'){
			arr[c-'A'].first++;
		}
		sort(arr, arr+N, cmp);
		
		for(int k=0, L=0, R=N-1, i, tmp ; k<N ; k++, i=0){
			if(k%2 == 0){
				// 放左邊
				
				// 先找到第一個還沒用到的數字
				while(used[arr[i].second - 'A'] && i+1<N) i++;
				
				// 確認這個數字是不是最後一個
				tmp = i;
				i++;
				while(used[arr[i].second - 'A'] && i+1<N) i++;
				// 不是最後一個的情況
				if(!(arr[tmp].first != arr[i].first && arr[i].second < arr[tmp].second)){
					i = tmp;
				}
				
				used[arr[i].second - 'A'] = true;
				ans_num[L] = arr[i].first;
				ans_chr[L] = arr[i].second;
				L++;
			}
			else{
				// 放右邊
				
				// 先找到第一個還沒用到的數字
				while(used[arr[i].second - 'A'] && i+1<N) i++;
				
				// 找到字典序最大的
				tmp = i;
				while(arr[tmp].first == arr[i+1].first && i+1<N){
					if(!used[arr[i+1].second - 'A']){
						tmp = i+1;
					}
					i++;
				}
				i = tmp;
				
				used[arr[i].second - 'A'] = true;
				ans_num[R] = arr[i].first;
				ans_chr[R] = arr[i].second;
				R--;
			}
		}
		
		for(int i=0 ; i<N ; i++){
			if(i) cout<<' ';
			cout<<ans_chr[i];
		}
		cout<<"\n";
		for(int i=0 ; i<N ; i++){
			if(i) cout<<' ';
			cout<<ans_num[i];
		}
		cout<<"\n";
	}
	return 0;
}

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