TIOJ 1225 . 數字合併

題目鏈接:https://tioj.ck.tp.edu.tw/problems/1225

又是一個Monotone queue的題目
維護一個單調遞減的stack
當有一個比top大的數字出現時
top必須被抹除才符合單調性
比較top左邊的數字和新加入的數字
選擇比較小的加入答案

以下為code

#include<bits/stdc++.h>

#include<bits/extc++.h>

using namespace std;

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

int main()

{

AC

int n,t;

ll r=0;

cin>>n;

stack<int> s;

while(n--)

{

cin>>t;

while(s.size()&&t>=s.top())

{

s.pop();

if(s.size()) r+=min(t,s.top());

else r+=t;

}

s.emplace(t);

}

while(s.size()>1)

{

s.pop();

r+=s.top();

}

cout<<r<<'\n';

}