# 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++`
Sign in with Wallet
Connect another wallet