题解：P12241 [蓝桥杯 2023 国 C] 最大区间

~~竟然没有人用悬线法。~~

思路：

我们可以假设以某一个

A_i

为最小值，使其向左右延伸。显然地，延伸的区间越长越好，那就可以用悬线法求出区间（即求出左右第一个大于它的位置。），最后求最大值即可。

悬线法：

定义

l_i

为当前找到的

i

位置的悬线能扩展到的最左边的位置，容易得到

l_i

初始为

i

，我们需要进一步判断还能不能进一步往左扩展。

如果当前

l_i = 1

，则已经扩展到了边界，不可以。

如果当前

a_i > a_{l_i - 1}

，则从当前悬线扩展到的位置不能再往左扩展了。

如果当前

a_i \le a_{l_i - 1}

，则从当前悬线还可以往左扩展，并且

l_i - 1

位置的悬线能向左扩展到的位置，

i

位置的悬线一定也可以扩展到，于是我们将

l_i

更新为

l_{l_i - 1}

，并继续执行判断（内容来自悬线法）。

代码：

CPP

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=3e5+5;
int n,ans;
long long a[N],l[N],r[N];
signed main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		l[i]=r[i]=i;
	}	
	for(int i=1;i<=n;i++)
		while(l[i]>1&&a[i]<=a[l[i]-1])l[i]=l[l[i]-1];
	for(int i=n;i>=1;i--)
		while(r[i]<n&&a[i]<=a[r[i]+1])r[i]=r[r[i]+1];
	for(int i=1;i<=n;i++)
		if((r[i]-l[i]+1)*a[i]>ans)
			ans=(r[i]-l[i]+1)*a[i];
	cout<<ans;
	return 0;
}

题解：P12241 [蓝桥杯 2023 国 C] 最大区间

文章操作

相关推荐

评论

题解：P12241 [蓝桥杯 2023 国 C] 最大区间