Gym - 101334F 单调栈

当时我的第一想法也是用单调栈，但是被我写炸了；我也不知道错在哪里；

看了大神的写法，用数组模拟的；

记录下单调递增栈的下标，以及每个数字作为最小值的最左边的位置。

当有数据要出栈的时候，说明栈里的数据已经不是最小了，右端点就是当前位置-1，那么就可以计算栈顶的元素所作的贡献；出栈完后，当前这个数字，他的最左边就是栈顶所能到达的位置；入栈；

#include <bits/stdc++.h>

using namespace std;

const int maxn =  + ;

int a[maxn];

int stacks[maxn];

long long sum[maxn];

int lef[maxn];

int main()

{

    freopen("feelgood.in","r",stdin);

    freopen("feelgood.out","w",stdout);

    int n;

    scanf("%d",&n);

    memset(sum,,sizeof(sum));

    memset(lef,,sizeof(lef));

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

        scanf("%d",&a[i]);

        sum[i] = sum[i-] + a[i];

    }

    a[++n] = -;

    int top = ;

    long long ans = -;

    int ansl = ,ansr = ;

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

        if(top==||a[i]>a[stacks[top-]]) {

            stacks[top++] = i;

            lef[i] = i;

            continue;

        }

        if(a[i]==a[stacks[top-]])

            continue;

        while(top>=&&a[i]<a[stacks[top-]]) {

            top --;

            long long tmp = (long long)a[stacks[top]]*(sum[i-]-sum[lef[stacks[top]]-]);

            if(tmp>ans) {

                ansr = i-;

                ansl = lef[stacks[top]];

                ans = tmp;

            }

        }

        lef[i] = lef[stacks[top]];

        stacks[top++] = i;

    }

    printf("%lld\n%d %d\n",ans,ansl,ansr);

    return ;

}

(之前的错误找到了ans=-1，可以都为0)

 #include <bits/stdc++.h>

 using namespace std;

 int n;

 const int maxn = +;

 struct num {

     long long value;

     int maxleft,maxright;

     int minleft,minright;

     num():maxleft(),maxright(),minleft(),minright(){}

 }a[maxn];

 stack<pair<int,int> > S;

 long long sum[maxn];

 void getMax()

 {

     while(!S.empty())

         S.pop();

     S.push(make_pair(a[].value,));

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

         while(!S.empty()&&S.top().first<=a[i].value) {

             //int value = S.top().first;

             int key = S.top().second;

             S.pop();

             a[i].maxleft +=a[key].maxleft;

             if(!S.empty()) {

                 a[S.top().second].maxright +=a[key].maxright;

             }

         }

         S.push(make_pair(a[i].value,i));

     }

     while(!S.empty()) {

         int key = S.top().second;

         S.pop();

         if(!S.empty()) {

             a[S.top().second].maxright +=a[key].maxright;

         }

     }

 }

 void getMin()

 {

     while(!S.empty())

         S.pop();

     S.push(make_pair(a[].value,));

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

         while(!S.empty()&&S.top().first>=a[i].value) {

             //int value = S.top().first;

             int key = S.top().second;

             S.pop();

             a[i].minleft +=a[key].minleft;

             if(!S.empty()) {

                 a[S.top().second].minright +=a[key].minright;

             }

         }

         S.push(make_pair(a[i].value,i));

     }

     while(!S.empty()) {

         int key = S.top().second;

         S.pop();

         if(!S.empty()) {

             a[S.top().second].minright +=a[key].minright;

         }

     }

 }

 int main()

 {

     freopen("feelgood.in","r",stdin);

     freopen("feelgood.out","w",stdout);

     scanf("%d",&n);

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

         scanf("%lld",&a[i].value);

         sum[i+] = sum[i] + a[i].value;

     }

    // getMax();

     getMin();

     int l = ;

     int r = ;

     long long ans = -;

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

         long long tmp = a[i].value*(sum[i+a[i].minright]-sum[i-a[i].minleft+]);

         if(ans<tmp) {

             ans = tmp;

             l = i - a[i].minleft + ;

             r = i + a[i].minright;

         }

     }

     printf("%lld\n%d %d\n",ans,l,r);

     return ;

 }

巴特西

Gym - 101334F 单调栈

最新文章

热门文章