【題解】Codeforces 1237D Balanced Playlist

【題目敘述】https://codeforces.com/contest/1237/problem/D
【解題想法】Monotonic Queue (單調隊列)

  • 讀入測資後,先複製兩份,接在原資料後方(總共三份)。
  • 下圖例說明,有時候會跨越到第三份資料才夠找出最長的播放清單。
  • 維護一個嚴格遞減的單調隊列,存放資料的index。
  • 維護條件:
    • dq.front() <= 2 * a[i]:否則,從dq前端開始pop,最後一個不滿足條件的index (now)及其前方尚未得到答案的所有index (j),都可以一併計算出答案 (i – j)。
    • dq.back() >= a[i]:否則,從dq後端開始pop,直到條件成立。
    • dq.push_back(i)
#include <iostream>
#include <deque>
using namespace std;
  
const int maxn = 1e5+5;
  
int n, a[maxn*3], mn = 1e9+5, mx = 0, ans[maxn], now, l;
deque <int> dq;
  
int main() {
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> a[i];
        a[i+n] = a[i];
        a[i+n*2] = a[i];
        mn = min(mn, a[i]);
        mx = max(mx, a[i]);
    }
    if (mx <= mn*2){
        for (int i = 0; i < n; i++){
            if (i != 0) cout << " ";
            cout << -1;
        }
        cout << "\n";
    }else{
        dq.push_back(0);
        l = 0;
        for (int i = 1; i < n*3; i++){
            if (!dq.empty() && a[dq.front()] > a[i]*2){
                while (!dq.empty() && a[dq.front()] > a[i]*2){
                    now = dq.front();
                    dq.pop_front();
                }
                for (int j = l; j <= now; j++){
                    ans[j] = i - j;
                }
                l = now+1;
            }
            while (!dq.empty() && a[dq.back()] < a[i]){
                dq.pop_back();
            }
            dq.push_back(i);
        }
        for (int i = 0; i < n; i++){
            cout << ans[i] << " ";
        }
        cout << "\n";
    }
}
分享本文 Share with friends