APCS 先加後乘與函數 (zerojudge j607)

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 369 所需閱讀時間 ≈ 1 分鐘

題目網址

給一個運算式，運算式的內容由數字、+、* 和 \(f()\) 某個函式 \(f()\) 所組成，除了函式 \(f()\) 以外不會有額外的括號。請將此運算式依照先加後乘的方式運算。

函式 \(f()\) 定義為從這個不定長度的參數 \(x_1, x_2, x_3, x_4, ...\) 中的最大值扣掉最小值。例如 \(f(3,6,2)=6-2=4\)，\(f(3)=0\)。

解題思路：
遇到 + 就直接加上去 遇到 * 先把後面做好 遇到 f 把到) 之前的每個數字記錄下來最後再比較

🌟可以一開始把) 的位置存起來，複雜度就可以是很漂亮的 \(O(N)\)，不過不用也沒關係，這題長度不超過 500，所以可以邊做邊找，複雜度到 \(O(N^2)\) 也沒什麼差，向我寫的程式就是邊做邊找的。

APCS 先加後乘與函數 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
#define int long long
using namespace std;

string in;
int len;

// 遇到+ 就直接加上去
// 遇到* 先把後面做好
// 遇到f 把到)之前的每個數字記錄下來最後再比較

int calculate(int idx, int sum){
    if(idx>=len || in[idx]==',' || in[idx]==')') return sum;
    if(in[idx] == '+') return calculate(idx+1, sum);
    if(in[idx] == '*') return sum*calculate(idx+1, 0);
    if(in[idx] == 'f'){
        int end_idx = idx, left_num=0;
        while(in[end_idx]!=')' || left_num>0) //可在一開始建好每個函數結尾位置，複雜度可縮短至O(N)
            end_idx++, left_num+=(in[end_idx]=='(')-(in[end_idx]==')'); 
        int Min = 100004, Max = -1;
        idx++; // '(' 的位置
        while(in[idx] != ')'){
            idx++;
            int cur = calculate(idx, 0);
            Min = min(Min, cur);
            Max = max(Max, cur);
            while(in[idx]!=',' && idx<end_idx) 
                idx++, left_num+=(in[idx]=='(')-(in[idx]==')');
        }
        return calculate(idx+1,sum+(Max-Min));
    }
    if(in[idx]>='0' && in[idx]<='9'){
        vector<int> add;
        int res = 0, pos=1;
        while(in[idx]>='0' && in[idx]<='9') add.push_back(in[idx++]-'0'), pos*=10;
        for(int i : add) pos/=10, res+=i*pos;
        return calculate(idx,sum+res);
    } return -1;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> in;
    in = "+" + in;
    len = in.size();
    cout << calculate(0, 0) << '\n';
    return 0;
}

PS：這題我上個月就寫了，但好像後來忘記丟上來 XD

AC的Submission～