題目網址
給一個運算式,運算式的內容由數字、+、* 和 \(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;
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) 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~