# 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';
}
```
:::
兩份解法的時間差異：
---
### [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;
}
}
```
:::
Sign in with Wallet
Connect another wallet