首页 > itarticle > UVa 11078 – Open Credit System

UVa 11078 – Open Credit System

admin 11月 13, 2020 0

Description

對於每組輸入，輸出 $a_i - a_j$ 的最大值，其中 $i < j$

Solution

對於 $n$ 可能到 $10^5$ ， $O(n^2)$ 暴力做明顯不行
仔細觀察可以發現，對於每個 $j$ 只要維護小於 $j$ 且 $a_i$ 最大的 $i$ 即可，與 $a_j$ 之數值無關
也就是說我們要維護一個遞減的數列
因其單調性，可使用隊列優化

Code

#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0);cin.tie(0)
#define endl 'n'

using namespace std;

int T, n, res;
deque<int> dq;

signed ()
{
    IO;
    cin >> T;
    while (T--) {
        cin >> n;
        res = INT_MIN;
        dq.clear();
        for (int i = 0, t; i < n; i++) {
            cin >> t;
            if (!dq.empty())
                res = max(res, dq.front() - t);
            while (!dq.empty() && dq.back() <= t)
                dq.pop_back();
            dq.push_back(t);
        }
        cout << res << endl;
    }
    return 0;
}