Codeforces 1313C.Skyscrapers

题目链接

题意是给你一个数组，问你如何建造，使得每个点都不小于其左右的点，包括不相邻的点

分析题意，容易得知，就是找一个点两侧的不上升序列且带修，那我们就分别从头跑一遍，从尾跑一遍，两者相加就是每个点的最大值

那我们可以利用单调栈来进行这个操作，注意初始化栈

这道题和CF1300E思想一样，都是用单调栈求最大不下降序列的和值，且可以进行修改

#include<bits/stdc++.h>

using namespace std;

#define lowbit(x) ((x)&(-x))

typedef long long LL;

typedef pair<int,int> pii;

const int maxn = 500003;

int buf[maxn], q[maxn];

LL s[maxn];

void run_case() {

    int n; cin >> n;

    for(int i = 1; i <= n; ++i) cin >> buf[i];

    LL sum = 0;

    int top = 0;

    q[0] = 0; // init stack

    for(int i = 1; i <= n; ++i) {

        while(top && buf[i] < buf[q[top]]) {

            int now = q[top--];

            sum -= 1LL * (now - q[top]) * buf[now];

        }

        sum += 1LL * (i - q[top]) * buf[i];

        s[i] += sum;

        q[++top] = i;

    }

    sum = 0, top = 0;

    q[0] = n+1; // init stack

    for(int i = n; i >= 1; --i) {

        while(top && buf[i] < buf[q[top]]) {

            int now = q[top--];

            sum -= 1LL * (q[top] - now) * buf[now];

        }

        sum += 1LL * (q[top] - i) * buf[i];

        s[i] += sum - buf[i];

        q[++top] = i;

    }

    int pos = max_element(s+1, s+1+n) - s;

    for(int i = pos-1; i >= 1; --i)

        buf[i] = min(buf[i], buf[i+1]);

    for(int i = pos+1; i <= n; ++i)

        buf[i] = min(buf[i], buf[i-1]);

    for(int i = 1; i <= n; ++i)

        cout << buf[i] << " ";

}

int main() {

    ios::sync_with_stdio(false), cin.tie(0);

    cout.flags(ios::fixed);cout.precision(10);

    //int t; cin >> t;

    run_case();

    cout.flush();

    return 0;

}

求一个点两边的性质可以跑两遍来实现

巴特西

Codeforces 1313C.Skyscrapers

最新文章

热门文章