upc组队赛1 小C的数学问题【单调栈】(POJ2796)

红太狼 2022-01-06 07:27 156阅读 0赞

#  #

小C的数学问题

## 题目描述 ##

小C是个云南中医学院的大一新生，在某个星期二，他的高数老师扔给了他一个问题。

让他在1天的时间内给出答案。

但是小C不会这问题，现在他来请教你。

请你帮他解决这个问题。

有n个数，每个数有权值。

数学老师定义了区间价值为区间和乘上区间内的最小值。

现在要你找出有最大区间价值的区间是什么，并输出区间价值。

## 输入 ##

每个输入文件只包含单组数据。  
第一行一个整数n。(1 <= n <= 100000)  
第二行n个整数a\_1,a\_2,...,a\_n。(0 <= a\_i <= 1000000)

## 输出 ##

第一行输出一个整数，表示最大的区间价值。  
第二行输出两个整数，表示区间的起点和终点。  
保证答案唯一。

## 样例输入 ##

6
    10 1 9 4 5 9

## 样例输出 ##

108
    3 6

## 题解 ##

原题POJ2796 用单调栈维护区间的最小值，复杂度就优化到了O(N)

## 代码 ##

#include<iostream>
    #include<cstdio>     //EOF,NULL
    #include<cstring>    //memset
    #include<cstdlib>    //rand,srand,system,itoa(int),atoi(char[]),atof(),malloc
    #include<cmath>           //ceil,floor,exp,log(e),log10(10),hypot(sqrt(x^2+y^2)),cbrt(sqrt(x^2+y^2+z^2))
    #include<algorithm>  //fill,reverse,next_permutation,__gcd,
    #include<string>
    #include<vector>
    #include<queue>
    #include<stack>
    #include<utility>
    #include<iterator>
    #include<iomanip>             //setw(set_min_width),setfill(char),setprecision(n),fixed,
    #include<functional>
    #include<map>
    #include<set>
    #include<limits.h>     //INT_MAX
    #include<cmath> // bitset<?> n
    using namespace std;
    #define rep(i,a,n) for(int i=a;i<n;i++)
    #define per(i,a,n) for(int i=n-1;i>=a;i--)
    #define fori(x) for(int i=0;i<x;i++)
    #define forj(x) for(int j=0;j<x;j++)
    #define memset(x,y) memset(x,y,sizeof(x))
    #define memcpy(x,y) memcpy(x,y,sizeof(y))
    #define all(x) x.begin(),x.end()
    #define readc(x) scanf("%c",&x)
    #define read(x) scanf("%d",&x)
    #define read2(x,y) scanf("%d%d",&x,&y)
    #define read3(x,y,z) scanf("%d%d%d",&x,&y,&z)
    #define print(x) printf("%d\n",x)
    #define lowbit(x) x&-x
    #define lson(x) x<<1
    #define rson(x) x<<1|1
    #define pb push_back
    #define mp make_pair
    #define N 100001
    typedef pair<int,int> P;
    typedef long long LL;
    typedef long long ll;
    const double eps=1e-8;
    const double PI = acos(1.0);
    const int INF = 0x3f3f3f3f;
    const int inf = 0x3f3f3f3f;
    const int mod = 1e9+7;
    const int MAXN = 1e6+7;
    const int maxm = 1;
    const int maxn = 100000 + 10;
    const ll MOD = 998244353;
    int a[maxn];
    int pos[maxn],st[maxn];
    ll sum[maxn];
    ll ans,tmp;
    int n;
    
    int main()
    {
        read(n);
        memset(sum, 0);
        for (int i = 0; i < n; i++){
            read(a[i]);
            sum[i] = sum[i - 1] + a[i]; // 前缀和 方便求区间的总和
        }
        a[n] = -1;
        ans = -1;
        int top = 0;
        int l, r;
        for (int i = 0; i <= n; i++){
            if (top == 0 || a[i] > a[st[top - 1] ]){ //如果比栈顶大 就入栈
                st[top++] = i;//单调栈的顶部
                pos[i] = i; //储存当前栈最小值延续到的左边界
            }
            else{
              while (top >= 1 && a[i] <= a[st[top - 1]]){ //如果ai比栈顶小,弹出所有比ai大的数
                  --top;
                  tmp = a[ st[top] ] * (sum[i - 1] - sum[pos[st[top]]-1]);
               //总价值 =  最小值（栈顶元素）  *  区间和（前缀和相减）
                  if (ans < tmp){ 
                      l = pos[st [top] ] + 1; 
                      r = i;
                      ans = tmp;
                  }
              }
              pos[i] = pos[st[top]];  // 以ai为最小值的区间左边界是他自己，从自己开始
              st[top++] = i; //入栈
            }
        }
        printf("%lld\n", ans);
        printf("%d %d\n", l, r);
        return 0;
    }

转载于:https://www.cnblogs.com/llke/p/10799971.html