P2422 良好的感觉

给定一段序列，其中元素 \(0 \leq a_{i} \leq 100000\)

定义一段子段 \([L, R]\) 的舒适值为 \(\min_{L \leq i \leq R}a_{i} * \sum_{i = L}^{R}a_{i}\)

求最大舒适值（并定位其位置）

\(n \leq 500000\)

Solution

首先 \(O(n^{2})\) 枚举区间，前缀和乱搞啥的显然不合理

考虑式子，后一项我们可以前缀和求出，于是重点放在 \(\min_{L \leq i \leq R}a_{i}\) 上

对于一个 \(a_{i}\)，贪心可知覆盖越广舒适值越大

枚举每一个 \(a_{i}\) 作为区间最小值，然后可以单调栈 \(O(1)\) 求出每个 \(d_{i}\) 对应的最长左区间

同理可以 \(O(n)\) 求出对应右端点

总复杂度 \(O(n)\)

Code

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#include<algorithm>

#include<climits>

#define LL long long

#define REP(i, x, y) for(LL i = (x);i <= (y);i++)

using namespace std;

LL RD(){

    LL out = 0,flag = 1;char c = getchar();

    while(c < '0' || c >'9'){if(c == '-')flag = -1;c = getchar();}

    while(c >= '0' && c <= '9'){out = out * 10 + c - '0';c = getchar();}

    return flag * out;

    }

const LL maxn = 200019, INF = 0xfffffffffffffff;

LL num;

LL a[maxn], sum[maxn];

LL l[maxn], r[maxn];

struct Stack{

	LL Index, val;

	}S[maxn];

LL top;

void get_l(){

	top = 0;

	S[++top].Index = 0;

	S[top].val = -INF;

	REP(i, 1, num){

		while(top >= 1 && S[top].val >= a[i])top--;

		l[i] = S[top].Index + 1;

		S[++top].Index = i;

		S[top].val = a[i];

		}

	}

void get_r(){

	top = 0;

	S[++top].Index = num + 1;

	S[top].val = -INF;

	for(LL i = num;i >= 1;i--){

		while(top >= 1 && S[top].val >= a[i])top--;

		r[i] = S[top].Index - 1;

		S[++top].Index = i;

		S[top].val = a[i];

		}

	}

int main(){

	while(scanf("%lld", &num) != EOF){

		memset(sum, 0, sizeof(sum));

		memset(a, 0, sizeof(a));

		memset(l, 0, sizeof(l));

		memset(r, 0, sizeof(r));

		REP(i, 1, num)a[i] = RD(), sum[i] = sum[i - 1] + a[i];

		get_l();

		get_r();

		LL ans = 0, L = 0, R = 0;

		REP(i, 1, num){

			if((sum[r[i]] - sum[l[i] - 1]) * a[i] >= ans){

				ans = (sum[r[i]] - sum[l[i] - 1]) * a[i];

				L = l[i], R = r[i];

				}

			}

		printf("%lld\n%lld %lld\n\n", ans, L, R);

		}

	return 0;

	}

巴特西

P2422 良好的感觉

P2422 良好的感觉

Solution

Code

最新文章

热门文章