CF1313C2 Skyscrapers (hard version) （單調堆疊）-有解無憂

Skyscrapers (hard version)

思路：我們需要維護當下標為inx的大樓為最高的時候，兩邊大樓的情況，我們可以把下標為inx的大樓最高時，分別統計左邊和右邊的情況，我們可以用單調堆疊維護最小值（小->大），如果堆疊頂的元素的高度小于inx的大樓，說明之前的所有大樓都因為堆疊頂的大樓而小于了inx的大樓的高度，如果堆疊頂的大樓高度大于等于inx的大樓，則說明堆疊頂下面第一個的大樓到堆疊頂的大樓之間的大樓需要改變為inx大樓的高度，需要注意空堆疊的情況，

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <algorithm>
  4 #include <functional>
  5 #include <set>
  6 #include <vector>
  7 #include <queue>
  8 #include <cstring>
  9 #include <stack>
 10  
 11 using namespace std;
 12  
 13 #define ll long long
 14 #define pb push_back
 15 #define fi first
 16 #define se second
 17  
 18  
 19 void solve(){
 20     int n;
 21     cin >> n;    
 22     vector<int > a(n);
 23     for(auto& in : a) cin >> in;
 24     stack<int > Sta;
 25     vector<ll > pre(n);
 26     for(int now = 0; now < n; ++now){
 27         while(!Sta.empty()){
 28             int top = Sta.top();
 29             if(a[top] >= a[now]){
 30                 Sta.pop();
 31                 if(!Sta.empty()){
 32                     pre[now] += (ll)a[now] * (top - (int)Sta.top());
 33                 }else {
 34                     pre[now] += (ll)a[now] * (top + 1);
 35                 }
 36             }else {
 37                 pre[now] += pre[top];
 38                 break;
 39             }
 40         }
 41         Sta.push(now);
 42         pre[now] += a[now];
 43     }
 44     // for(int i = 0; i < n; ++i) cout << pre[i] << " ";
 45     // cout << endl;
 46     vector<ll > rpre(n);
 47     while(!Sta.empty()) Sta.pop();
 48     vector<int > cp(a);
 49     reverse(a.begin(), a.end());
 50     for(int now = 0; now < n; ++now){
 51         while(!Sta.empty()){
 52             int top = Sta.top();
 53             if(a[top] >= a[now]){
 54                 Sta.pop();
 55                 if(!Sta.empty()){
 56                     rpre[now] += (ll)a[now] * (top - (int)Sta.top());
 57                 }else {
 58                     rpre[now] += (ll)a[now] * (top + 1);
 59                 }
 60             }else {
 61                 rpre[now] += rpre[top];
 62                 break;
 63             }
 64         }
 65         Sta.push(now);
 66         rpre[now] += a[now];
 67     }
 68     // for(auto& x : rpre) cout << x << " ";
 69     // cout << endl;
 70     int inx = 0;
 71     //cp[i]被算了兩次，需要減去一次
 72     for(int i = 1; i < n; ++i){
 73         inx = (pre[i] + rpre[n - 1 - i] - cp[i] > pre[inx] + rpre[n - 1 - inx]  - cp[inx] ? i : inx);
 74     }
 75     // cout << "inx = " << inx << endl;
 76     int Min = cp[inx];
 77     vector<int > ans(n);
 78     for(int i = inx; i >= 0; --i){
 79         Min = min(Min, cp[i]);
 80         ans[i] = Min;
 81     }
 82     Min = cp[inx];
 83     for(int i = inx + 1; i < n; ++i){
 84         Min = min(Min, cp[i]);
 85         ans[i] = Min;
 86     }
 87     for(auto x : ans) cout << x << " ";
 88     cout << endl;
 89  
 90 }
 91  
 92 int main(){
 93     
 94     ios::sync_with_stdio(false);
 95     cin.tie(0);
 96     cout.tie(0);
 97     solve();
 98     
 99     return 0;
100 }

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/55363.html

標籤：其他

上一篇：堆疊的鏈接存盤

下一篇：資料結構（C語言版）---排序