UVa11890 - Calculus Simplified(貪心)

題目大意

給你一個只有加減的多元方程式與一些數字，EX: \(-(-(x-x))\)，\(x = 2,3\)，請將這些 x 帶入方程式內，並找出一種方程式帶入 x 後可以輸出最大的數字。
每一個 x 只能夠使用一次

題目連結

重點觀念

• 英文閱讀(對，這個對我來說太麻煩了….)
• 將方程式做拆解

分析

• 我們需要解決的問題是將方程式做拆解，然後讓所有帶有負號的 \(x\) 放入最小的數字，讓正 \(x\) 都帶入最大的數字。
• 當運算遇到負號時，x 會改變其正負。
• 因此我們需要做到
  • 紀錄每一個 x 的正負
  • 並透過 pair<int,int> 保存正 x 有幾個、負 x 有幾個
  • 正 x 帶入最大的數字、負 x 帶入最小的數字
• 現在我們來講講如何實現八
  • 由於我們要解決括號的問題，因此我們可以用一個 stack 來儲存到現在為止我們經過幾個正、負
  • 並且用一個 post 標記，來表示這組括號內都是正 or 負
  • 當碰到右括號時，看看 stack.top()
    • 如果是負號，就需要把 post 相反，因為我們已經離開現在這組帶有負項的括號，所以要變號
    • 正數則不用改變。
    • stack.pop()

參考連結

Uva11890 -Calculus Simplified by txya900619

心得

有點被考倒了QQ。原本是很貪心的只想要紀錄現在經過了幾個 +,-，然後直接做成一個 pair，完全忘記括號的問題了…orz。

然後想到這個問題後，花了 5min 還想不出來要怎麼解決括號。
題外話：我原本還想用前序、後序去解，不過後來發現有更好的寫法，只要用 stack 記錄經過的括號，離開這組括號時在 pop 這組括號的符號即可。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define int long long
#define LOCAL
#define DEBUG
#define MAXN 100020
using namespace std;
int t, n, num[MAXN];
string formula; //題目方程式

pair<int,int> process(){
    pair<int,int> x; //first 表示正的 x 有幾個、second 負 x 有幾個
    bool post = true; //展開方程式後，當前這組括號是正還是負 post true plus, false subtract
    stack<bool> status; //儲存經過的每組括號正負
    for(int i = 0; i < formula.length(); i++){
        if(formula[i] == 'x'){ 
            bool op = post; //這一個 x 是正或是負 operator true plus, false subtract
            if(i != 0 && formula[i-1] == '-') op = !op; //如果這項 x 是負，那就需要變號
            if(op) x.first++; 
            else x.second++;
        }

        if(formula[i] == '('){ //經過這組括號
            if(i != 0 && formula[i-1] == '-'){ //這組括號是負號
                post = !post;
                status.push(false);
            }
            else status.push(true);
        }
        if(formula[i] == ')'){ //離開這組括號
            if(status.top() == false) post = !post; //如果這組括號是負號，那我們再把它變回來
            status.pop();
        }
    }
    return x;
}

int32_t main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> formula >> n;
        for(int i = 0; i < n; i++) cin >> num[i];
        sort(num, num+n);
        pair<int,int> x = process();

        int ans = 0;
        for(int i = 0; i < x.second; i++) ans -= num[i];
        for(int i = 0; i < x.first; i++) ans += num[n-i-1];
        cout << ans << '\n';
    }
    return 0;

}