# 2022/01/08 APCS Python題解

### 第一題
* 簡單list運用

https://zerojudge.tw/ShowProblem?problemid=j605


while True:
    try:
        k = int(input())
        times = []
        score = []
        for _ in range(k):
            t, s = map(int, input().split())
            times.append(t)
            score.append(s)
        res = max(score)-k-score.count(-1)*2
        print(0 if res < 0 else res, times[score.index(max(score))])
    except:
        break

:::warning
:bulb: 也可邊讀入邊計算, 最後記得判斷正負
:::
---

### 第二題
* 字串處理
* 模擬

https://zerojudge.tw/ShowProblem?problemid=j606


while True:
    try:
        k, q, r = map(int, input().split())
        s = input()
        permutes = []
        for _ in range(q):
            tmp = [0]*k
            for i, p in enumerate(map(int, input().split())):
                tmp[p-1] = s[i]
            permutes.append(tmp)
            s = ''.join(tmp)
        res = list(zip(*permutes))
        for i in range(r):
            print(''.join(res[i]))
    except:
        break

:::warning
:bulb: 按照題意一步一步解, 可以畫圖方便理解
:::

___

### 第三題
* Stack
* 遞迴
* 其他特殊解法(.split(), .replace())

https://zerojudge.tw/ShowProblem?problemid=j607

def calculator(s):  # 運算先加後乘
    s = s.split('*')
    ret = 1
    for i in s:
        ret *= eval(i)
    return ret


while True:
    try:
        num_stk = []  # 儲存運算元
        op_stk = []  # 儲存運算子
        num = ''
        for word in input():
            if word.isdigit():
                num += word
            else:
                if num:
                    num_stk.append(num)
                    num = ''

                if word == 'f': continue
                if word in '(*+':
                    op_stk.append(word)
                else:  # word == ',' or ')'
                    formula = ''
                    while op_stk[-1] in '+*':  # 取得算式
                        if not formula:
                            formula += num_stk.pop()
                        formula += op_stk.pop()+num_stk.pop()

                    if formula:
                        num_stk.append(str(calculator(formula)))

                    if word == ',':
                        op_stk.append(word)
                    else:  # word == ')' --> 運算 f()
                        func_list = [int(num_stk.pop())]
                        while op_stk[-1] != '(':
                            func_list.append(int(num_stk.pop()))
                            op_stk.pop()
                        op_stk.pop()
                        value = str(max(func_list)-min(func_list))
                        num_stk.append(value)

        # 最後剩下num, *, +
        if num: num_stk.append(num)
        formula = num_stk.pop()
        while op_stk:
            formula += op_stk.pop()+num_stk.pop()
        print(calculator(formula))
    except:
        break

:::warning
:bulb: 依照目前元素一一判斷是否要從stack取出元素.
word共有以下情況:
* 數字 : 放進num_stk
* '+', '*' ==> 放進op_stk
* '(', ',' ==> 運算式是否結束的依據
* ')' ==> f()結束
:::

___

### 第四題
* 貪婪
* 排程問題

https://zerojudge.tw/ShowProblem?problemid=j608
:::danger
#更:利用Binary Search加快效率
:::

while True:
    try:
        n, k = map(int, input().split())
        start = map(int, input().split())
        finish = map(int, input().split())

        activity = list(zip(start, finish))
        activity.sort(key=lambda x: (x[1], x[0]))  # 先依結束時間，後按開始時間

        machine_endtime = [-1]*k  # 每台機器目前活動的結束時間
        res = 0

        # selected = set()  # 選擇的活動時段

        for i in range(n):
            machine_endtime.sort()
            l, r, start_time = -1, k, activity[i][0]
            # 利用Binary Search尋找endtime最接近start_time的機器
            while l+1 < r:
                mid = (l+r)//2
                if machine_endtime[mid] < start_time:
                    l = mid
                else:
                    r = mid
            if start_time <= machine_endtime[l]:
                continue
            machine_endtime[l] = activity[i][1]
            # selected.add(activity[i])
            res += 1

        print(res)
        # print(selected)
    except:
        break

# 舊版本
while True:
    try:
        n, k = map(int, input().split())
        start = map(int, input().split())
        finish = map(int, input().split())

        activity = list(zip(start, finish))
        activity.sort(key=lambda x: (x[1], x[0]))  # 先依結束時間，後按開始時間

        machine = [-1]*k  # 每台機器目前活動的結束時間
        res = 0

        # selected = set()  # 選擇的活動時段

        for i in range(n):
            idx = -1  # 此輪活動選擇的機器
            distance_time = float('inf')
            for j in range(k):  # 遍歷每台機器
                if activity[i][0] <= machine[j]: continue
                if activity[i][0]-machine[j] < distance_time:  # 找空閒時間最接近開始時間的機器
                    idx = j
                    distance_time = activity[i][0]-machine[j]
            if idx != -1:
                machine[idx] = activity[i][1]
                # selected.add(activity[i])
                res += 1

        print(res)
        # print(selected)
    except:
        break

:::warning
:bulb: 時間複雜度為O(n*k), python會超時, 底下附上ChatGPT修改的C++版本
:::

#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    int n, k;
    while(cin >> n >> k) {
        int start[n], finish[n];
        for (int i = 0; i < n; i++) {
            cin >> start[i];
        }
        for (int i = 0; i < n; i++) {
            cin >> finish[i];
        }
        pair<int, int> activity[n];
        for (int i = 0; i < n; i++) {
            activity[i] = make_pair(start[i], finish[i]);
        }
        sort(activity, activity+n, [](pair<int, int> a, pair<int, int> b) {
            return (a.second < b.second) || (a.second == b.second && a.first < b.first);
        });

        int machine[k];
        for (int i = 0; i < k; i++) {
            machine[i] = -1;
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            int idx = -1;
            int distance_time = INT_MAX;
            for (int j = 0; j < k; j++) {
                if (activity[i].first <= machine[j]) continue;
                if (activity[i].first-machine[j] < distance_time) {
                    idx = j;
                    distance_time = activity[i].first-machine[j];
                }
            }
            if (idx != -1) {
                machine[idx] = activity[i].second;
                res += 1;
            }
        }
        cout << res << endl;
    }
    return 0;
}

___