louisfghbvc的部落格

題目大意:  算積水容積。

思路:  WTF。Leetcode 42 簡單版。隨便O(N^2) 或是 啥暴力應該都可解。這邊用O(N) 

紀錄右邊的最大值。之後迭代更新左邊最大值。取左右兩邊較小值。代表說容積等於左右較小-當前位置。

代碼:  

#include <bits/stdc++.h>

#define Fast cin.tie(0), ios::sync_with_stdio(0)
#define louisfghbvc int t; cin >> t; while(t--)
using namespace std;

void solve(){
    int n;
    cin >> n;
    vector<int> arr(n);
    for(auto &it: arr) cin >> it;

    vector<int> suf(n);
    suf[n-1] = arr[n-1];
    for(int i = n-2; i >= 0; --i) suf[i] = max(suf[i+1], arr[i]);

    int ans = 0, mxl = arr[0];
    for(int i = 1; i+1 < n; ++i){
        ans += max(0, min(mxl, suf[i+1])-arr[i]);
        mxl = max(mxl, arr[i]);
    }
    cout << ans << "\n";
}

int main()
{
    Fast;
    louisfghbvc
        solve();
    return 0;
}

/**
2
7
3 2 1 4 2 3 5
12
4 6 3 1 2 9 8 7 4 6 5 2
**/