## 排序與搜尋
### 1/3 社課
---
## 排序
----
### 排序
Python 中的排序可以透過呼叫 `sorted()` 或 `a.sort()` 來進行
----
### [ZeroJudge - 排序](https://zerojudge.tw/ShowProblem?problemid=a104)
```py
while True:
try:
n = int(input())
a = list(map(int, input().split()))
print(*sorted(a))
except:
break
```
----
### [ZeroJudge - 排序](https://zerojudge.tw/ShowProblem?problemid=a104)
```py
while True:
try:
n = int(input())
a = list(map(int, input().split()))
a.sort()
print(*a)
except:
break
```
----
### `sorted()` 和 `a.sort()` 的差別
`sorted()` 把串列複製一份進行排序
```py
a = [5, 1, 3, 2, 4]
b = sorted(a)
print(a)
print(b)
```
輸出：
```bash
[5, 1, 3, 2, 4]
[1, 2, 3, 4, 5]
```
----
### `sorted()` 和 `a.sort()` 的差別
`a.sort()` 在原串列進行排序
```py
a = [5, 1, 3, 2, 4]
b = a.sort()
print(a)
print(b)
```
輸出：
```bash
[1, 2, 3, 4, 5]
None
```
----
### [ZeroJudge - 二維點排序](https://zerojudge.tw/ShowProblem?problemid=a915)
給定 $n$ 個二維平面上的點，要求你把他們按照以 $x$ 軸坐標為第一關鍵字， $y$ 軸坐標為第二關鍵字的方式從小到大來進行排序
----
### [ZeroJudge - 二維點排序](https://zerojudge.tw/ShowProblem?problemid=a915)
- tuple 的比較預設由第一個元素開始比較，相同才會比較第二個
- 直接用 tuple 來排序
----
### [ZeroJudge - 二維點排序](https://zerojudge.tw/ShowProblem?problemid=a915)
```py
n = int(input())
a = [(0, 0)] * n
for i in range(n):
a[i] = tuple(map(int, input().split()))
a.sort()
for i in range(n):
print(*a[i])
```
---
## Lambda 函式
----
### Lambda 函式
這裡只介紹 Lambda 函式在排序的應用
Lambda 函式的詳細介紹可以看[這裡](https://www.w3schools.com/python/python_lambda.asp)
----
### [ZeroJudge - 二維點排序](https://zerojudge.tw/ShowProblem?problemid=a915)
- 分別輸入 `x[i]` 、 `y[i]`
- 比較時再以索引來排序
- 排序時直接建立該索引的 tuple 來比較
----
### [ZeroJudge - 二維點排序](https://zerojudge.tw/ShowProblem?problemid=a915)
```py
n = int(input())
x, y = [0] * n, [0] * n
od = [i for i in range(n)]
for i in range(n):
x[i], y[i] = map(int, input().split())
od.sort(key = lambda i : (x[i], y[i]))
for i in range(n):
print(x[od[i]], y[od[i]])
```
----
### [YTP - 一級棒](https://oj.ntucpc.org/problems/434)
給定⼀個班級所有學⽣的成績，請你輸出成績最⾼的同學的名字。
----
### [YTP - 一級棒](https://oj.ntucpc.org/problems/434)
- 用成績來排序即可
- 成績高到低排序，可以用 `sort()` 內建的 `reverse`
----
### [YTP - 一級棒](https://oj.ntucpc.org/problems/434)
```py
n = int(input())
s = [("", 0)] * n
for i in range(n):
t = input().split()
s[i] = (t[0], int(t[1]))
s.sort(reverse = True, key = lambda x : x[1])
print(s[0][0])
```
----
### [ZeroJudge - 明明愛排列](https://zerojudge.tw/ShowProblem?problemid=a225)
排序數字，先看個位數，把個位數由小到大排。如果個位數字一樣的話，將這些數字由大至小排。
----
### [ZeroJudge - 明明愛排列](https://zerojudge.tw/ShowProblem?problemid=a225)
- 把個位數和完整數字包裝成 tuple 排序
----
### [ZeroJudge - 明明愛排列](https://zerojudge.tw/ShowProblem?problemid=a225)
```py
while True:
try:
n = int(input())
a = list(map(int, input().split()))
a.sort(key = lambda x : (x % 10, -x))
print(*a)
except:
break
```
----
### [TOJ - 打獵分配問題](https://toj.tfcis.org/oj/pro/15/)
- 複雜的排序
----
### [TOJ - 打獵分配問題](https://toj.tfcis.org/oj/pro/15/)
```py
import sys
e = sys.stdin.readline
pri = {"elder" : 1, "nursy" : 2, "kit" : 3, "warrior" : 4, "appentice" : 5, "medicent" : 6, "deputy" : 7, "leader" : 8}
while True:
try:
n, m = map(int, e().split())
a = [(0, 0, "")] * n
for i in range(n):
t = e().split()
a[i] = (pri[t[1]], int(t[2]), t[0])
a.sort(key = lambda x : (x[0], x[1] if x[0] == 5 else -x[1], x[2]))
m = min(n, m)
for i in range(m):
print(a[i][2])
except:
break
```
----
### `cmp_to_key()`
- functools 中的函式
- 在 `cmp_to_key()` 中放一個 Lambda 函式，包含兩個參數
- 若兩數須交換，帶入 Lambda 函式後為正
- 若兩數相等，帶入 Lambda 函式後為零
- 若兩數不須交換，帶入 Lambda 函式後為負
----
### [ZeroJudge - 二維點排序](https://zerojudge.tw/ShowProblem?problemid=a915)
```py
from functools import cmp_to_key
n = int(input())
x, y = [0] * n, [0] * n
for i in range(n):
x[i], y[i] = map(int, input().split())
od = [i for i in range(n)]
od.sort(key = cmp_to_key(lambda i, j : y[i] - y[j] if x[i] == x[j] else x[i] - x[j]))
for i in range(n):
print(x[od[i]], y[od[i]])
```
---
## 應用
----
### [Codeforces - Progressive Square](https://codeforces.com/contest/1955/problem/B)
----
### [Codeforces - Progressive Square](https://codeforces.com/contest/1955/problem/B)
- 先假設 $a_{1,1}=0$ ，把這個 progressive square 的所有元素都放入一個串列
- 把 $a$ 和 $b$ 都排序
- 比較 $a$ 和 $b$ 每一個元素的差，如果有不相同答案即為 `NO` ，否則為 `YES`
----
### [Codeforces - Progressive Square](https://codeforces.com/contest/1955/problem/B)
```py
t = int(input())
for _ in range(t):
n, c, d = map(int, input().split())
a, b = [], list(map(int, input().split()))
for i in range(n):
for j in range(n):
a.append(c * i + d * j)
a.sort()
b.sort()
for i in range(n * n):
if a[i] - b[i] != a[0] - b[0]:
print("NO")
break
if i == n * n - 1:
print("YES")
```
----
### [APCS - 物品堆疊](https://zerojudge.tw/ShowProblem?problemid=c471)
----
### [APCS - 物品堆疊](https://zerojudge.tw/ShowProblem?problemid=c471)
- 假設有 $A$ 、 $B$ 兩物，尋找 $A$ 置於 $B$ 前的條件
- 若 $A$ 放上面，拿 $B$ 時花 $w(A)\times f(B)$ 的能量
- 若 $B$ 放上面，拿 $A$ 時花 $w(B)\times f(A)$ 的能量
- 以 $w(A)\times f(B)$ 與 $w(B)\times f(A)$ 來排序
----
### [APCS - 物品堆疊](https://zerojudge.tw/ShowProblem?problemid=c471)
```py
import sys
from functools import cmp_to_key
e = sys.stdin.readline
n = int(e())
a = [[0, 0]] * n
w = list(map(int, e().split()))
f = list(map(int, e().split()))
for i in range(n):
a[i] = [w[i], f[i]]
a.sort(key = cmp_to_key(lambda x, y : x[0] * y[1] - y[0] * x[1]))
a.append((0, 0))
for i in range(n):
a[i][0] += a[i - 1][0]
ans = 0
for i in range(n):
ans += a[i][1] * a[i - 1][0]
print(ans)
```
---
## 二分搜
----
### 猜數字遊戲
- 在範圍 $[1,1000]$ 裡猜一個數字 $n$
- 如果猜的數字 $x<n$ 會告訴你太小了
- 如果猜的數字 $x>n$ 會告訴你太大了
- 怎麼猜比較快？
----
### 猜數字遊戲
- 如果猜了一個數字 $x<n$ 那就表示 $\le x$ 的數都不可能是 $n$
- 猜的範圍變小了
----
### 猜數字遊戲
- 每次都猜範圍內的最中間
- 每次範圍都會少一半
----
### [ZeroJudge - 二分搜尋法](https://zerojudge.tw/ShowProblem?problemid=d732)
```py
n, k = map(int, input().split())
a = list(map(int, input().split()))
x = list(map(int, input().split()))
for i in range(k):
l, r = 0, n
while l < r - 1:
mid = (l + r) // 2
if a[mid] <= x[i]:
l = mid
else:
r = mid
if a[l] == x[i]:
print(l + 1)
else:
print(0)
```
----
### [ZeroJudge - 二分搜尋法](https://zerojudge.tw/ShowProblem?problemid=d732)
```py
import bisect
n, k = map(int, input().split())
a = list(map(int, input().split()))
x = list(map(int, input().split()))
for i in range(k):
pos = bisect.bisect_left(a, x[i]);
if a[pos] == x[i]:
print(pos + 1)
else:
print(0)
```
----
### [CSES - Factory Machines](https://cses.fi/problemset/task/1620/)
- 有一家工廠擁有 $n$ 台機器，每台機器都可以用來生產產品。你的目標是總共生產 $t$ 件產品。
- 對於每台機器，你知道它生產一件產品所需的秒數。這些機器可以同時運作，你可以自由決定它們的工作排程。
- 求完成生產 $t$ 件產品所需的最短時間是多少？
----
### [CSES - Factory Machines](https://cses.fi/problemset/task/1620/)
- 如果時間 $x$ 可以完成生產 $t$ 件產品，則 $\sum_{i=1}^{n}\lfloor\frac{x}{k_i}\rfloor\ge t$
- 對 $x$ 二分搜
----
### [CSES - Factory Machines](https://cses.fi/problemset/task/1620/)
```py
n, t = map(int, input().split())
k = list(map(int, input().split()))
def cal(mid):
ret = 0
for i in range(n):
ret += mid // k[i]
return ret
l, r = 0, 10 ** 18
while l < r - 1:
mid = (l + r) // 2
if cal(mid) < t:
l = mid
else:
r = mid
print(r)
```
----
### [CSES - Factory Machines](https://cses.fi/problemset/task/1620/)
- Python 3.10 以後 `bisect()` 裡面可以放 `key`
- 但是 Zerojudge Python 版本太舊實用性不高
----
### [CSES - Factory Machines](https://cses.fi/problemset/task/1620/)
```py
import bisect
n, t = map(int, input().split())
k = list(map(int, input().split()))
def cal(mid):
ret = 0
for i in range(n):
ret += mid // k[i]
return ret
pos = bisect.bisect_left(range(10 ** 18), t, key = lambda x : cal(x))
print(pos)
```
----
### [CSES - Array Division](https://cses.fi/problemset/task/1085/)
- 給定一個包含 $n$ 個正整數的陣列。
- 你的任務是將這個陣列分成 $k$ 個子陣列，使得子陣列中最大總和的值盡可能小。
----
### [CSES - Array Division](https://cses.fi/problemset/task/1085/)
- 最大總和的值越大，子陣列數量越小
- 二分搜最大總和的值
----
### [CSES - Array Division](https://cses.fi/problemset/task/1085/)
```py
n, k = map(int, input().split())
x = list(map(int, input().split()))
def cal(mid):
ret, cur = 0, 0
for i in range(n):
if cur + x[i] > mid:
cur = 0
ret += 1
cur += x[i]
if cur > 0:
ret += 1
return ret
l, r = max(x) - 1, (10 ** 9) * (2 * 10 ** 5) + 1
while l < r - 1:
mid = (l + r) // 2
if cal(mid) > k:
l = mid
else:
r = mid
print(r)
```
{"title":"排序與搜尋","contributors":"[{\"id\":\"3aeed4e7-1118-47e7-b0cc-18caea236427\",\"add\":10024,\"del\":1099}]","description":"今天不會教排序的原理，只會教排序要怎麼用"}