题目链接：http://acm.uestc.edu.cn/#/problem/show/771
最大容积
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
在 xx 轴的正整数坐标 1,2,⋯,N1,2,⋯,N 上分别竖立着一条线段，高度分别为 h1,h2,⋯,hNh1,h2,⋯,hN。这样只要我们任意选择两条线段 i,ji,j，再加上 xx 轴就能围成一个水槽了(只不过是二维的)。
由于短板效应，这个水槽的容积应该是
V=S×h=|j−i|×min(hi,hj)V=S×h=|j−i|×min(hi,hj)
那么选哪两条线段与 xx 轴构成的水槽容积最大呢？
Input
输入一共两行：
第一行是一个正整数 NN，代表一共有多少条线段，其中 2<N<1062<N<106；
第二行是 NN 个正整数 h1,h2,⋯,hNh1,h2,⋯,hN，分别表示线段 1,2,⋯,N1,2,⋯,N 的高度，其中 0≤hi<1030≤hi<103。
Output
输出最大容积。
Sample input and outpu
| Sample Input | Sample Output |
|---|---|
5 |
6 |
题解：今天和老房讨论了这个题，方法是枚举左端点，优化右区间。关键是怎么优化。二分不行，线段树搞不通，最后老房灵机一动，想出用后缀和来搞，再次发现前缀和后缀和真的真的很神奇，后缀和记录大于等于某个数字的最远位置，然后枚举左区间，即使每个高度非常高，复杂度也就n+h.然后发现这个题标程有问题。看下文。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1e6+;
int arr[maxn];
int h[];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&arr[i]);
for(int i=n;i>=;i--)
{
if(!h[arr[i]])
{
int cur = arr[i];
while(h[cur]==&&cur>)
{
h[cur] = i;
cur--;
}
}
}
int ans = ;
for(int i=;i<=n;i++)
{
int cur = abs(h[arr[i]]-i)*arr[i];
ans = max(ans,cur);
}
printf("%d\n",ans);
return ;
}
卷珠帘
这份代码ac了，然后他们给我发了一组数据，5 5 4 3 2 1输出的是0,因为还需要从前往后扫一遍，，，QAQ
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1e6+;
int arr[maxn];
int h2[];
int h1[];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&arr[i]);
for(int i=n;i>=;i--)
{
if(!h2[arr[i]])
{
int cur = arr[i];
while(h2[cur]==&&cur>)
{
h2[cur] = i;
cur--;
}
}
}
for(int i=;i<=n;i++)
{
if(!h1[arr[i]])
{
int cur = arr[i];
while(h1[cur]==&&cur>)
{
h1[cur] = i;
cur--;
}
}
}
int ans = ;
for(int i=;i<=n;i++)
{
int cur = abs(h2[arr[i]]-i)*arr[i];
ans = max(ans,cur);
}
for(int i=n;i>=;i--)
{
int cur = abs(h1[arr[i]]-i)*arr[i];
ans = max(ans,cur);
}
printf("%d\n",ans);
return ;
}
卷珠帘