---
# System prepended metadata

title: Week 7：排序一、二
tags: [S3 公開資源]

---

# Week 7：排序一、二

###### tags: `S3 公開資源`

:::info
時間：03/12 9:00 ~ 17:00
地點：成大計算機與網路中心 **75201** 教室
主題：排序一、二
直播連結：https://youtube.com/live/pE71zOwnWg4?feature=share
:::

# 必作題題解

[TOC]

## 二章 - 第七節

<!-- ### [題目](連結) -->

### [UVa 10327 - Flip Sort](http://domen111.github.io/UVa-Easy-Viewer/?10327)

撰寫者：fishhh

實作一次 bubble sort 就好
這個東西有一個專有名詞：逆序數對

最佳複雜度可以在 $O(N\log N)$ 內完成。

:::spoiler 參考程式碼
```cpp=
#include "iostream"
using namespace std;
int ary[2010]={};
int main(){
	int n;
	while(cin>>n){
		for(int i=0;i<n;i++)cin>>ary[i];
		bool change = 0;
		int cnt=0;
		for(int i=0;i<n;i++){
			change = 0;
			for(int j=0;j<n-i-1;j++){
				if(ary[j]>ary[j+1]){
					swap(ary[j],ary[j+1]);
					change = 1;
					cnt++;
				}
			}
			if(!change)break;
		}
		// for(int i:ary)cout<<i<<" ";
		cout<<"Minimum exchange operations : "<<cnt<<"\n";
	}

}
```
:::

---

### [No - Judge 名次查詢](https://hackmd.io/@sa072686/cp/%2Foj2gvDtjT0mfKJVhlmJeng#名次查詢)

撰寫者：Eason

直接由大而小排序，就可以$O(1)$查詢

:::spoiler 合併排序
```cpp=
#include<iostream>
using namespace std;

long long arr[200005];

void merge (int l, int r){
    int mid = (l + r) / 2;

    if (l == r) return;

    merge (l, mid);
    merge (mid + 1, r);

    int sorted[200005];

    int lp = l, rp = mid + 1, p = l;
    while (lp <= mid && rp <= r){
        if (arr[lp] > arr[rp]){
            sorted[p] = arr[lp];
            lp++;
            p++;
        }
        else{
            sorted[p] = arr[rp];
            rp++;
            p++;
        }
    }

    while (lp <= mid){
        sorted[p] = arr[lp];
        lp++;
        p++;
    }
    while (rp <= r){
        sorted[p] = arr[rp];
        rp++;
        p++;
    }

    for (int i = l; i <= r; i++){
        arr[i] = sorted[i];
    }

    return;
}

int main(){
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> arr[i];
    }
    merge (0, n - 1);

    int q;
    cin >> q;
    for (int i = 0; i < q; i++){
        int temp;
        cin >> temp;
        cout << arr[temp - 1] << '\n';
    }

    return 0;
}
```
:::

:::spoiler 快速排序
```cpp=
#include<iostream>
using namespace std;

int arr[200005];

void quick_sort(int l, int r){
    if (l >= r) return;

    int tar = (l + r) / 2;
    int i = l;

    for (int ind = l + 1; ind <= r; ind++){
        if (arr[ind] > arr[tar]){
            i++;
            swap (arr[i], arr[ind]);
        }
    }

    swap (arr[tar], arr[i]);

    quick_sort(l, i - 1);
    quick_sort(i + 1, r);

    return;
}

int main(){
    ios::sync_with_stdio(0), cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> arr[i];
    }
    quick_sort(0, n - 1);

    int q;
    cin >> q;
    for (int i = 0; i < q; i++){
        int temp;
        cin >> temp;
        cout << arr[temp - 1] << '\n';
    }
    return 0;
}
```
:::

---
### [No - Judge 集合比較](https://hackmd.io/@sa072686/cp/%2Fys2z9BntSh-_6mZTIPNy1Q#%E9%9B%86%E5%90%88%E6%AF%94%E8%BC%83)

撰寫者：ｆｉｓｈｈｈ

這裡使用 merge sort 完成排序。

:::spoiler
```cpp=
#include "iostream"
using namespace std;
int ary[2010][2]={};
int temp[2010][2]={};
void merge(int l,int r,int ay);
void split(int l,int r,int ay){ //這裡是 [l,r] (閉區間)
	if(l==r)return;
	int m = (l+r)/2;
	split(l,m,ay);
	split(m+1,r,ay);
	merge(l,r,ay);
	return ;
}
void merge(int l,int r,int ay){
	int m = (l+r)/2;
	int pt1=l,pt2=(l+r)/2+1;
	for(int i=l;i<=r;i++){
		if(pt1 > m){ //左半邊已經拿完了
			temp [i][ay] = ary[pt2++][ay];
		}
		else if(pt2==r+1){ //右半邊已經拿完了
			temp [i][ay] = ary[pt1++][ay];
		}
		else if(ary[pt1][ay]>ary[pt2][ay]){
			temp[i][ay] = ary[pt1++][ay];
		}
		else{
			temp[i][ay] = ary[pt2++][ay];
		}
	}
	for(int i=l;i<=r;i++)ary[i][ay]=temp[i][ay];
	return ;
}

int main(){
	int n,m;
	cin>>n>>m;
	if(n!=m){
		cout<<"not equal\n";
		return 0;
	}
	for(int i=1;i<=n;i++)cin>>ary[i][0];
	for(int i=1;i<=m;i++)cin>>ary[i][1];
	split(1,n,0);
	split(1,m,1);

	for(int i=1;i<=n;i++){
		if(ary[i][0]!=ary[i][1]){
			cout<<"not equal\n";
			// cout<<ary[i][0]<<" "<<ary[i][1]<<"!";
			return 0;
		}
	}

	// for(int i=1;i<=n;i++){
	// 	cout<<ary[i][0]<<" ";
	// }

	cout<<"equal\n";
	return 0;

}
```
:::

---

### [No Judge 種類統計](https://hackmd.io/@sa072686/cp/%2Fys2z9BntSh-_6mZTIPNy1Q#%E7%A8%AE%E9%A1%9E%E7%B5%B1%E8%A8%88)

撰寫者：小麥

先sort再掃描一次並紀錄次數

:::spoiler
```cpp=
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>

using namespace std;

vector<long long> arr;

void solve() {
    int n;
    cin >> n;
    arr.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    sort(arr.begin(), arr.end());

    int counter = 0;
    int type_counter = 0;
    stringstream ans;
    for (int i = 1; i < n; i++) {
        if (arr[i] != arr[i - 1]) {
            ans << arr[i - 1] << ": " << counter << " times" << "\n";
            counter = 0;
            type_counter++;
        }
        counter++;
    }
    ans << arr[n - 1] << ": " << counter << " times" << "\n";

    cout << (type_counter + 1) << " type\n" << ans.str() << '\n';
}

int main() {
    solve();

    return 0;
}
```
:::

---

### [ZJ b966 - 線段覆蓋長度](https://zerojudge.tw/ShowProblem?problemid=b966)

撰寫者：Koying

講義有提供合併線段的解法，參考程式如下

:::spoiler Code
```cpp=
#include <bits/stdc++.h>
#define ll unsigned long long

using namespace std;
pair<int,int> v[10005]; 


signed main()
{
    int n;
    cin >> n 
    for(int i=0;i<n;i++) {
        cin >> v[i].first >> v[i].second;
    }
    sort(v,v+n); // 1,2 4,8 5,6 7,9
    int a=v[0].first,b=v[0].second;
    int ans=0;
    for(int i=0;i<n;i++)
    {
        if(v[i].first>b)
        {
            ans+=b-a;
            a=v[i].first;
            b=v[i].second;
        } 
        else if((v[i].second)>b) b=v[i].second;

    }
    ans+=b-a;
    cout<<ans<<endl; 
    
    


    return 0;
}
```
:::

#### 另解 1（只需陣列的解法）：

可以觀察到，對於一個被線段覆蓋的區間（如 $[1, 5]$ 就是一個被 $[1, 4], [2, 5]$ 兩線段覆蓋的區間），其起終點一定是一個線段的起終點，因此我們只需要記錄所有線段的起點與終點位置即可。

假設有一個線段 $[1, 4]$，我們在 $1$ 的位置紀錄為 $+1$，代表這個位置多了一條線段，並在 $4$ 的位置紀錄為 $-1$，代表這個位置少了一條線段。

最後，將紀錄的數字做前綴和後得到的結果，就是每個位置的線段覆蓋**厚度**。只要計算 $> 0$ 的塊數就是答案。

時間複雜度：$\mathcal{O}(10^7)$

:::spoiler Code
```cpp=
#include <bits/stdc++.h>

using namespace std;

int x[10005], y[10005];
int cnt[10000005];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
        cnt[x[i]]++;
        cnt[y[i]]--;
    }
    int ans = 0;
    for (int i = 0; i < 10000005; i++) {
        cnt[i] += cnt[i - 1];
        ans += (cnt[i] > 0);
    }
    cout << ans << '\n';
}
```
:::

#### 另解 2（使用排序 + struct / pair）

同樣是使用紀錄頭尾的技巧，我們將頭尾座標及狀態包成一個 struct or pair（例如線段 $[1, 4]$ 包成 $(1, +1), (4, -1)$）並用陣列紀錄。

接著我們將這個陣列依照第一個元素（座標）排序，得到的結果便是從左到右的**狀態更新順序**。

接著我們就可以依序對每次狀態更新進行計算，並記錄以下變數：
- $now$：上一次更新到哪
- $cur$：現在座標
- $cnt$：線段覆蓋厚度
- $ans$：答案

對於每種狀態更新，只有兩種情況：
1. 原本沒有線段覆蓋，現在多了一個
2. 原本有線段覆蓋，現在多或少了一個

可以發現，能夠修改答案的情況只有第二種，因為在這個座標之前就有線段覆蓋了，所以我們就可以將答案 $ans$ 加上 $cur - now$，並將 $now$ 更新為 $cur$，就可以得到最終的答案

:::spoiler Code
```cpp=
#include <bits/stdc++.h>

using namespace std;

pair<int, int> e[20005];

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        e[i * 2] = {x, 1};
        e[i * 2 + 1] = {y, -1};
    }

    sort(e, e + n * 2);

    int ans = 0, now = 0, cnt = 0;
    for (int i = 0; i < n * 2; i++) {
        if (cnt == 0) {
            cnt += e[i].second;
            now = e[i].first;
        }
        else {
            cnt += e[i].second;
            ans += e[i].first - now;
            now = e[i].first;
        }
        
    }
    cout << ans << '\n';
}
```
:::

兩份解法的時間差異：
![](https://hackmd.io/_uploads/HkZpca513.png)


---

### [Kattis oddmanout - Odd Man Out](https://open.kattis.com/problems/oddmanout)

撰寫者：fishh

排序好之後，相同的兩個就會被放在一起。
可以知道一件事，如果 $ary[i]$ 是那個要被踢出去的，那麼前面一定都會兩兩成對。也就是說，前面的元素個數一定是"偶數個"。

:::spoiler 參考程式碼
```cpp=
#include<iostream>
using namespace std;
unsigned long long temp[10000],arr[10000],n;
void merge(int s,int e){
    int h=s,t,mid=(s+e)/2;
    t=mid+1;
    for(int d=s;d<=e;d++){
        if(t>e){
            temp[d]=arr[h];
            h++;        
        }
        else if(h>mid){
            temp[d]=arr[t];
            t++;
        }
        else if(arr[h]>arr[t]){
            temp[d]=arr[h];
            h++;
        }
        else{
            temp[d]=arr[t];
            t++;
        }
    }
    for(int i=s;i<=e;i++){
        arr[i]=temp[i];
    }
}
void spit(int s,int e){
    int mid=(e+s)/2,qq;
    if(s==e){
//      cout<<s;
        return ;
    }
    spit(s,mid);
    spit(mid+1,e);
    merge(s,e);  
}
int main(){
    int n,q;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>q;
        cout<<"Case #"<<i<<": ";
        for(int x=0;x<q;x++){
            cin>>arr[x];
        } 
        spit(0,q-1);
        for(int x=0;x<q;x+=2){
            if(arr[x]!=arr[x+1]){
                cout<<arr[x]<<"\n";
                break;
            }
        }
    }
    
}
```
:::

---

### [Kattis recount - Recount](https://open.kattis.com/problems/recount)

撰寫者：fishhh

題目的意思就是要算每個人得到了幾票，輸出票數最高的人
這邊偷下一章會講到的 sort 內建函數來用。

:::spoiler
```cpp=
#include "iostream"
#include "algorithm"
using namespace std;
string ary[100010]={};
int main(){
	int n=0;
	string s;
	while(getline(cin,s)){
		if(s=="***")break;
		ary[n++]=s;
	}
	sort(ary,ary+n);
	int cnt=1,maxcnt=0;
	bool same=0;
	string ans=ary[0];
	ary[n] = ary[n-1]+"..";
	for(int i=1;i<=n;i++){
		if(ary[i]!=ary[i-1]){
			if(cnt>maxcnt){
				maxcnt=cnt;
				same=0;
				ans = ary[i-1];
			}
			else if(cnt==maxcnt)same=1;
			cnt=1;
		}
		else cnt++;
	}
	if(same){
		cout<<"Runoff!\n";
	}
	else{
		cout<<ans;
	}
}
```
:::


