---
# System prepended metadata

title: 0-11 struct、0-12 變數的作用範圍及0-13 排序
tags: [演算法, C++, APCS, Python]

---

# 0-11 struct、0-12 變數的作用範圍及0-13 排序

講義不是我寫的，網址在此 https://emanlaicepsa.github.io/2020/10/21/0-index/
我只是將自己寫的練習題程式碼記錄下來。
最後更新日期：2024年10月6日

## [ZeroJudge: a104. 排序](https://zerojudge.tw/ShowProblem?problemid=a104)

### Python 程式碼

執行時間最久約為 23 ms，使用記憶體最多約為 3.6 MB，通過測試。
```python=
import sys

for line in sys.stdin:
    n = int(line)
    data = list(map(int, sys.stdin.readline().split()))
    data.sort()
    print(*data)
```

### C++ 程式碼

執行時間最久約為 9 ms，使用記憶體最多約為 276 kB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n; 
    while(cin >> n) {
        int data[n];
        for(int i=0; i<n; i++) cin >> data[i];
        sort(data, data+n);
        for(int i=0; i<n; i++) cout << data[i] << " \n"[i == n-1];
    }
}
```

## [ZeroJudeg: a233. 排序法~~~ 挑戰極限](https://zerojudge.tw/ShowProblem?problemid=a233)

### Python 程式碼

執行時間最久約為 0.9 s，使用記憶體最多約為 64.6 MB，通過測試。
```python=
n = int(input())
data = list(map(int, input().split()))
data.sort()
print(*data)
```

### C++ 程式碼

執行時間最久約為 0.5 s，使用記憶體最多約為 2.2 MB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n; cin >> n; 
    int data[n];
    for(int i=0; i<n; i++) cin >> data[i];
    sort(data, data+n);
    for(int i=0; i<n; i++) cout << data[i] << " \n"[i == n-1];
    return 0;
}
```

## [ZeroJudge: a915. 二維點排序](https://zerojudge.tw/ShowProblem?problemid=a915)

### Python 程式碼

寫法1，用 functools 函式庫的 cmp_to_key 自訂比較式。執行時間最久約為 33 ms，使用記憶體最多約為 4.2 MB，通過測試。
```python=
import functools

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def mycmp(p1, p2):
    if p1.x > p2.x:
        return 1
    elif p1.x == p2.x:
        if p1.y > p2.y: return 1
        else: return -1
    else:
        return -1

n = int(input())
points = []
for _ in range(n):
    x, y = map(int, input().split())
    points.append(Point(x, y))

points.sort(key=functools.cmp_to_key(mycmp))
for point in points:
    print("{:d} {:d}".format(point.x, point.y))
```

寫法2，用二維串列儲存資料再排序。執行時間最久約為 24 ms，使用記憶體最多約為 3.8 MB，通過測試。
```python=
n = int(input())
points = []
for _ in range(n):
    points.append(list(map(int, input().split())))

points.sort()
for point in points: print(*point)
```

### C++ 程式碼

執行時間最久約為 3 ms，使用記憶體最多約為 348 kB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
using namespace std;

struct Point {
    int x, y;
};

bool mycmp(Point p1, Point p2) {
    if (p1.x != p2.x) return p1.x < p2.x;
    else return p1.y < p2.y;
}

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int n; cin >> n;
    Point points[n];
    for(int i=0; i<n; i++) cin >> points[i].x >> points[i].y;
    sort(points, points+n, mycmp);
    for(int i=0; i<n; i++) cout << points[i].x << " " << points[i].y << "\n";
    return 0;
}
```

執行時間最久約為 3 ms，使用記憶體最多約為 344 kB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;

int main() {
    ios::sync_with_stdio(0),cin.tie(0);
    int n; cin >> n;
    pair<int, int> points[n];
    for(int i=0; i<n; i++) cin >> points[i].first >> points[i].second;
    sort(points, points+n);
    for(int i=0; i<n; i++) cout << points[i].first << " " << points[i].second << "\n";
    return 0;
}
```

## [TOJ: 15 / 打獵分配問題](https://toj.tfcis.org/oj/pro/15/)

### Python 程式碼

第3筆測資超時。
```python=
from functools import cmp_to_key
import sys

def mycmp(a, b):  # 資料依序為身份、年齡、名字
    if a[0] > b[0]: return 1  # 身份編號大的放後面
    elif a[0] < b[0]: return -1  # 身份編號小的放前面
    elif a[1] != b[1]:  # 身份編號相同，而且年齡不同
        if a[0] == 5 and b[0] == 5:  # 身份編號都是 5
            if a[1] > b[1]: return 1  # 年齡大的放後面
            elif a[1] < b[1]: return -1  # 年齡小的放前面
            else:  # 年齡相同
                if a[2] > b[2]: return 1  # 名字字典順序大的放後面
                else: return -1  # 名字字典順序小的放前面
        else:  # 身份編號相同而且都不是5號
            if a[1] < b[1]: return 1  # 年齡小的放後面
            elif a[1] > b[1]: return -1  # 年齡大的放前面
            else:  # 年齡相同
                if a[2] > b[2]: return 1  # 名字字典順序大的放後面
                else: return -1  # 名字字典順序小的放前面
    else:  # 身份編號相同、年齡相同
        if a[2] > b[2]: return 1  # 名字字典順序大的放後面
        else: return -1  # 名字字典順序小的放前面

role = {"elder": 1, "nursy": 2, "kit": 3, "warrior": 4,
        "appentice": 5, "medicent": 6, "deputy": 7, "leader": 8}

for line in sys.stdin:
    n, m = map(int, line.split())
    cats = []
    for _ in range(n):
        na, ro, yr = input().split()
        cats.append([role[ro], int(yr), na])
    cats.sort(key = cmp_to_key(mycmp))
    if n < m: m = n
    for i in range(m): print(cats[i][2])
```

### C++ 程式碼

執行時間最久約為 763 ms，使用記憶體最多約為 10612 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;

struct Cat {  // 自訂類別
    string name;  // 名字
    int role, year;  // 身份、年齡
};

bool mycmp(Cat a, Cat b) {  // 自訂比較式
    if (a.role != b.role) {  // 如果身份不同
        return a.role < b.role;  // 依照身份編號由小到大排序
    } else if (a.year != b.year) {  // 如果身份相同而且年齡不同
        if (a.role == 5 && b.role == 5) return a.year < b.year;  // 如果身份都是 appentice，依照年齡由小到大排序
        else return a.year > b.year;  // 其它身份，依照年齡由大到小排序
    } else return a.name < b.name;  // 如果身份、年齡都相同，依照名字字典順序排序
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    map<string, int> roles = {{"elder", 1}, {"nursy", 2}, {"kit", 3}, {"warrior", 4},  // 身份對應的編號
                              {"appentice", 5}, {"medicent", 6}, {"deputy", 7}, {"leader", 8}};
    int n, m;  // 貓的數量 n，食物數量 m
    while(cin >> n >> m) {  // 多筆測資
        Cat cats[n];  // 儲存 n 隻貓資料的陣列
        for(int i=0; i<n; i++) {  // 讀取 n 隻貓的資料
            string na, ro; int yr;
            cin >> na >> ro >> yr;
            cats[i].name = na; cats[i].role = roles[ro]; cats[i].year = yr;
        }
        sort(cats, cats+n, mycmp);  // 依照 mycmp 排序
        if (n < m) m = n;  // 如果 n 小於 m，重設 m 為 n
        for(int i=0; i<m; i++) cout << cats[i].name << "\n";  // 輸出前 m 隻貓的名字
    }
    return 0;
}
```

## [TOJ: 539 / B. 國手](https://toj.tfcis.org/oj/pro/539/)

### Python 程式碼

執行時間最久約為 644 ms，使用記憶體最多約為 36900 kB，通過測試。
```python=
n, k = map(int, input().split())  # 天數 n，標準 k
a = list(map(int, input().split()))  # 裝弱的分數
b = list(map(int, input().split()))  # 正常發揮的分數
d = [0]*n  # 正常發揮的分數 - 裝弱的分數
tot = 0  # 裝弱的分數總和
for i in range(n):  # 依序讀取每天的分數
    d[i] = b[i] - a[i]  # 更新第 i 天的分差
    tot += b[i]  # 更新 tot
# end of for loop
d.sort()  # 分差由小到大排序
flag = True  # 是否及格
for i in range(n):  # 依序檢查 n 項
    if tot - d[i] < k:  # 如果 tot 減去當天裝弱的分差小於 k
        print(i)  # 印出 i，即為可以裝弱的天數
        flag = False  # 已經不及格
        break  # 中止迴圈
    tot -= d[i]  # 更新總分，扣掉分差
# end of for loop
if flag: print(n)  # 如果 n 天都裝弱仍然及格，印出 n
```

### C++ 程式碼

這題要用 long long，用 int 會溢位。執行時間最久約為 52 ms，使用記憶體最多約為 5080 kB，通過測試。
```cpp=
#include <iostream>
#include <algorithm>
typedef long long LL;
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    LL n, k; cin >> n >> k;  // 天數 n，標準 k
    LL a[n], b[n], d[n], tot = 0;  // 裝弱的分數a，正常發揮的分數b，b-a，b的總和
    for(LL i=0; i<n; i++) cin >> a[i];  // 依序讀取a
    for(LL i=0; i<n; i++) {
        cin >> b[i];  // 依序讀取b
        d[i] = b[i] - a[i];  // 更新第 i 天的分差
        tot += b[i];  // 更新 tot
    }
    sort(d, d+n);  // 分差由小到大排序
    bool flag = true;  // 是否及格
    for(LL i=0; i<n; i++) {  // 依序檢查 n 項
        if (tot - d[i] < k) {  // 如果 tot 減去當天裝弱的分差小於 k
            cout << i << "\n";  // 印出 i，即為可以裝弱的天數
            flag = false;  // 已經不及格
            break;  // 中止迴圈
        }
        tot -= d[i];  // 更新總分，扣掉分差
    }
    if (flag) cout << n << "\n";  // 如果 n 天都裝弱仍然及格，印出 n
    return 0;
}
```

## [ZeroJudge: c471. 物品堆疊](https://zerojudge.tw/ShowProblem?problemid=c471)

以下內容引用自另一篇文章〈[APCS實作題2017年10月第4題：物品堆疊 (Stacking)](https://hackmd.io/@yizhewang/r1LDMAH0s)〉

{%hackmd @yizhewang/r1LDMAH0s %}


## [TOJ: 11 / bubble](https://toj.tfcis.org/oj/pro/11/)

這題不能真的跑氣泡排序，一定會超時。改用 C++ 及合併排序計算次數還是超時。

### Python 程式碼

```python=

```

### C++ 程式碼

```cpp=

```

------

###### tags:`演算法`、`APCS`、`Python`、`C++`