# APCS 2023 1月 實作

### [P1](https://zerojudge.tw/ShowProblem?problemid=j605) 迴圈、最大值
變數很多，最大值的初始值要小於零，總分為負也要記得判斷，否則只有部分分

#include <iostream>
using namespace std;
int main() {
    int k; 
    cin >> k;
    int mx = -1, fail = 0;
    int tp; //時間點
    for(int i=0, t, s;i<k;i++){
        cin >> t >> s;
        if(s == -1){
            fail++;
        }
        else if(s > mx){
            tp = t;
            mx = s;
        }
    }
    int score = mx - k - fail * 2;
    if(score < 0) score = 0;
    cout << score << " " << tp;
    return 0;
}

### [P2](https://zerojudge.tw/ShowProblem?problemid=j606) 字串、二維陣列

#include<iostream>
using namespace std;

int main(){
    int k, q, r; cin >> k >> q >> r;
    string s;
    cin >> s;

    string tmp[q];
    for(int i=0;i<q;i++){
        tmp[i] = s; //copy s
        for(int j=0, p;j<k;j++){
            cin >> p;
            tmp[i][p-1] = s[j];
        }
        s = tmp[i];
    }
    for(int i=0;i<r;i++){
        for(int j=0;j<q;j++){
            cout << tmp[j][i];
        }
    }
    return 0;
}

### [P3](https://zerojudge.tw/ShowProblem?problemid=j607) 遞迴、stack
將運算式歸納為f()、g()兩個函式，其中g()主要處理加乘運算。思路為遇到加號就進行運算，其餘放入stack內，待終止時，再將所有數字相乘並回傳

#include <bits/stdc++.h>
using namespace std;

string s;
int idx;
long long g();
long long f(){
    idx+=2; //pass "f("
    long long mx = 0;
    long long mn = 1e17;
    while(s[idx]!=')'){
        if(s[idx] == ','){
            idx++; continue;
        }
        long long k = g();
        mx = max(mx, k);
        mn = min(mn, k);
    }
    return mx-mn;
}

long long g(){
    stack<long long> num;
    stack<char> sym;
    while(idx<s.size() && s[idx] != ',' && s[idx] != ')'){
        if(isdigit(s[idx])){
            int st = idx;
            while(idx < s.size() && isdigit(s[idx])){
                idx++;
            }
            num.push(stoi(s.substr(st, idx-st)));
            if(!sym.empty() && sym.top() == '+'){
                long long a = num.top(); num.pop();
                long long b = num.top(); num.pop();
                num.push(a+b);
                sym.pop();
            }
            idx--;
        }else if(s[idx] == 'f'){
            num.push(f());
            if(!sym.empty() && sym.top() == '+'){
                long long a = num.top(); num.pop();
                long long b = num.top(); num.pop();
                num.push(a+b);
                sym.pop();
            }
        }else if(s[idx] == '+'){
            sym.push('+');
        }else if(s[idx] == '*'){
            sym.push('*');
        }
        idx++;
    }
    long long result = num.top();
    num.pop();
    while(!num.empty()){
        result = result * num.top();
        num.pop();
    }
    return result;
}


int main() {
    cin >> s;
    cout << g();
    return 0;
}

#### 30%解

#include <bits/stdc++.h>
using namespace std;

int main() {
    string s;
    cin >> s;
    
    stack<long long> num;
    stack<char> sym;
    for(int idx=0;idx<s.size();idx++){
        //非數字即符號
        if(isdigit(s[idx])){
            int st = idx;
            while(idx < s.size() && isdigit(s[idx])){
                idx++;
            }
            
            num.push(stoi(s.substr(st, idx-st)));
            if(!sym.empty() && sym.top() == '+'){
                long long a = num.top(); num.pop();
                long long b = num.top(); num.pop();
                num.push(a+b);
                sym.pop();
            }
            idx--;
        }else{ //sym
            sym.push(s[idx]);
        }
    }
    long long result = num.top();
    num.pop();
    while(!num.empty()){
        result = result * num.top();
        num.pop();
    }
    cout << result;
    return 0;
}

### [P4](https://zerojudge.tw/ShowProblem?problemid=j608) greedy、二分搜、multiset
需要可舉辦的活動盡可能多，以下列二greedy條件達成：1.優先選擇結束時間早的活動舉辦(留給後面的時間越多，自然有更多活動可舉辦)，2.每場活動安排結束時間最晚的機器，結束時間早的機器可以留給後面的活動

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n, k; cin >> n >> k;
    vector<pair<int, int>> v(n);
    for(int i=0;i<n;i++){
        cin >> v[i].second; 
    }
    for(int i=0;i<n;i++){
        cin >> v[i].first; //結束時間在前，方便排序
    }
    sort(v.begin(), v.end());

    multiset<int> right_k; //機器上一次租借到何時
    for(int i=0;i<k;i++){ //k台，均未被租借
        right_k.insert(-1); 
    }
    int ans = 0;
    for(int i=0;i<n;i++){ //對n場活動進行greedy
        auto it = right_k.lower_bound(v[i].second); //第一台不行的機器
        if(it == right_k.begin()){ //沒有機器可安排
             continue;
        }
        ans++;
        //update
        right_k.erase(prev(it)); //安排前面那台機器
        right_k.insert(v[i].first); //更新結束時間
    }
    cout << ans;
    return 0;
}

#### 40%解

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int n, k; cin >> n >> k; //k=1
    vector<pair<int, int>> v(n);
    for(int i=0;i<n;i++){
        cin >> v[i].second;
    }
    for(int i=0;i<n;i++){
        cin >> v[i].first; //結束時間在前，方便排序
    }

    sort(v.begin(), v.end());

    int ans = 0;
    int pre = -1; //機器上一次結束時間
    for(int i=0;i<v.size();i++){
        if(v[i].second <= pre) continue;
        ans++;
        pre = v[i].first;
    }
    cout << ans;
}