题解 UVA1619
Mr_think
2020-12-31 15:05:55
## [UVA1619 感觉不错 Feel Good](https://www.luogu.com.cn/problem/UVA1619)
## 题目大意：
给出正整数n和一个$(1 <= n <= 100 000)$长度的数列，要求找出一个子区间，使这个子区间的数字和乘上子区间中的最小值最大。输出这个最大值与区间的两个端点。
## solution:
很暴力的去想，我们可以枚举区间$[l,r]$,遍历这个区间找到最小值，同时算出区间和。但很明显时间复杂度爆炸$O(N^3)$
我们再审一遍题：
```
使这个子区间的数字和乘上子区间中的最小值最大
```
既然枚举区间行不通，不妨试着枚举**最小值**：对于每一个数列中的数字 $a_i$ ，找到当它作为数列最小值时最长的序列，得到序列的端点 $l,r$。预处理前缀和，通过$a[r]-a[l-1]$求出区间的和，乘这个最小值$a[i]$最后取一个$max$
## 接下来是细节的处理：
我们想要找到当$a[i]$作为最小值的最长序列，就要找到$a[i]$左边、右边最后一个比它大的数，或者说找到第一个**比它小的数**，左右分别为$a[l]$、$a[r]$,我们想要得到的左端点、右端点就为：$l+1$、$r-1$
现在我们请出主角：[**单调栈**](https://www.luogu.com.cn/problem/P5788)
~~在这不多做赘述，不会的自己看看吧~~
具体操作见代码：
```cpp
//找右端第一个比a[i]小的数，把右端点赋成i-1
for(int i=1;i<=n;i++)
{
while(top&&a[i]<a[st[top]])
you[st[top--]]=i-1;
st[++top]=i;
}
while(top) you[st[top--]]=n;//剩下的就是没找到比它小的，就将右端点r赋成n
//找左端第一个比a[i]小的数，把左端点赋成i+1
for(int i=n;i>=1;i--)
{
while(top&&a[i]<a[st[top]])
zuo[st[top--]]=i+1;
st[++top]=i;
}
while(top) zuo[st[top--]]=1;同理，没找到将左端点l赋值成1
```
再处理下前缀和
```cpp
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
p[i]=p[i-1]+a[i];
}
```
~~完结撒……~~**此题还有很多坑点**
UVA是多组输入 我们需要
```cpp
while(scanf("%d",&n)!=EOF)
```
此题**没有**SPJ，需要在最大值相同时，使区间尽量**短**，于是出现了下面的判断：
```cpp
long long now;//不开long long见祖宗
now=a[i]*(p[you[i]]-p[zuo[i]-1]);//当前乘积
if(now>ans||(now==ans&&you[i]-zuo[i]<dy-dz))
{
ans=now;
dz=zuo[i];dy=you[i];//保存答案
}
```
平均下来时间复杂度$O(N)$
看到这的同学，可以自己去写代码了(~~tf口吻~~)
[还是给你们吧[手动滑稽]](https://www.luogu.com.cn/paste/xnya0dek)
### End
## 作者的碎碎念：
作为一个初三党，做题的时间可谓少之又少，写题解就更不用说了，这是刚期末考试完才抽出时间写的，觉得有帮助的话就点个赞，谢谢了