39 条题解
-
1
朱广恩 LV 6 @ 2016-11-12 21:38:00
*****const maxn=100000;
var h,l,r:array[0..maxn+1]of longint;
var i,max,n,k:longint;
begin
while not eof do
begin
max:=0;
read(n);
h[0]:=0;h[n+1]:=0;//*数据一直在变，这一次的数据可能会dai到下一次
for i:=1 to n do read(h[i]); readln;
for i:=1 to n do
begin
l[i]:=i; //k:=i-1;
while (h[i]<=h[l[i]-1])and(h[i]>0) do l[i]:=l[l[i]-1]; //***会出现和h[i]=0。。。***
end;
for i:=n downto 1 do
begin
r[i]:=i;
while (h[i]<=h[r[i]+1])and(h[i]>0) do r[i]:=r[r[i]+1];
end;
for i:=1 to n do
if (r[i]-l[i]+1)*h[i]>max then max:=(r[i]-l[i]+1)*h[i];writeln(max);
end;
writeln('0');
end.**** -
1
var i,j,m,n,s,t,jj,tot:longint;
a,b,f:array[0..500000] of longint;//以一个为节点向前,向后查找,其高度大于当前值，就继续找；否则退出；
begin
while not eof do
begin
read(n);
tot:=0;
fillchar(a,sizeof(a),0);
for i:=1 to n do
read(a[i]);
readln;
for i:=1 to n do
begin
j:=i; jj:=i;
while (jj>1) and (a[jj-1]>=a[i]) do dec(jj);
while (a[i]<=a[j+1]) and (j<n) do inc(j);
s:=a[i]*(j-jj+1);
if s>tot then tot:=s;
end;
writeln(tot);
end;
writeln('0');
end. -
0
#1 Accepted 278ms 1.387 MiB
假定一个位置为一个矩形的最小高度，以这个位置向两边扩展直到左右分别遇到第一个小于选定最小高度的数，可用单调栈，代码如下
#include <bits/stdc++.h>
using namespace std;
int n,h[100005],r[100005],l[100005],z[100005];
int main()
{
while(scanf("%d",&n)==1)
{
long long maxx=-1;
for(int i=1;i<=n;i++)
{
scanf("%d",&h[i]);
r[i]=i+1; l[i]=i-1;
}
int k=0;
for(int i=1;i<=n;i++)
{
while(h[z[k]]>=h[i] && k>0)
{
r[z[k]]=i;
k--;
}
l[i]=z[k];
z[++k]=i;
}
for(int i=1;i<=n;i++)
{
long long t=h[i];
t=t*(r[i]-l[i]-1);
if(t>maxx) maxx=t;
}
printf("%d\n",maxx);
}
printf("0");
return 0;
} -
0
玛德，就是最后输入0后面
多加了一个换行就一直TLE
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}const int N = 100000 + 5;
int n, h[N], s[N], pos[N];
int main() {
while (scanf("%d", &n) == 1) {
int top = 0;
for (int i = 1; i <= n; i++) {
h[i] = read();
while (top && h[i] <= h[s[top]]) top--;
pos[i] = s[top] + 1;
s[++top] = i;
}
top = 0; s[0] = n + 1;
int ans = 0;
for (int i = n; i >= 1; i--) {
while (top && h[i] <= h[s[top]]) top--;
ans = max(ans, (s[top] - pos[i]) * h[i]);
s[++top] = i;
}
printf("%d\n", ans);
}
printf("0");
return 0;
}-
WeiSama @ 2017-01-25 22:04:53
*输出
-
-
0
program fg;
var l,q,w,r,a:array[0..100000]of longint;
i,j,n,m,k,h,t,ans:longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a)
else exit(b);
end;begin
while not eof do
begin
ans:=-maxlongint;
read(n);
for i:=1 to n do
read(a[i]);
readln;
h:=1;t:=1;l[1]:=1;q[1]:=1;
for i:=2 to n do
begin
while (h<=t)and(a[q[t]]>=a[i]) do
dec(t);
l[i]:=q[t];
inc(t);
q[t]:=i;
end;
h:=1;t:=1;w[1]:=n;w[0]:=n+1;
r[n]:=n;
for i:=n-1 downto 1 do
begin
while (h<=t)and(a[w[t]]>=a[i]) do dec(t);
r[i]:=w[t];
inc(t);
w[t]:=i;
end;
for i:=1 to n do
ans:=max(ans,(r[i]-l[i]-1)*a[i]);
writeln(ans);
end;
writeln(0);
end. -
0
program vj1580;
var a,l,r:array[0..100001] of longint;
n,i:longint;
max:int64;
begin
while not eof do
begin
read(n);
for i:=1 to n do read(a[i]);readln;
a[0]:=-maxlongint;a[n+1]:=-maxlongint;for i:=1 to n do
begin
l[i]:=i-1;
while a[l[i]]>=a[i] do l[i]:=l[l[i]];
end;for i:=n downto 1 do
begin
r[i]:=i+1;
while a[r[i]]>=a[i] do r[i]:=r[r[i]];
end;max:=0;
for i:=1 to n do
if (r[i]-l[i]-1)*a[i]>max then max:=(r[i]-l[i]-1)*a[i];
writeln(max);
end;
writeln(0);
end.m67大牛教导我们
O（n）求每一个元素前第一个比他小的 -
0
yzl609271536 LV 10 @ 2009-10-22 16:20:45
编译通过...
├ 测试数据 01：答案正确... 88ms
---|---|---|---|---|---|---|---|-
Accepted 有效得分：100 有效耗时：88ms莫名其妙。。。
-
0
huyuanming11 LV 10 @ 2009-08-21 15:37:27
做了这题，得出一个重要结论：在VIJOS上用EOF是愚蠢的！
-
0
fammiebright LV 9 @ 2009-08-09 12:38:38
不就是个标准的最大子矩形嘛……
测试数据 01：运行超时|无输出...经过本人的N+M次提交，终于明白了怎么回事：
只有 while not eof是不行的，因为最后有个空格或空行什么的。所以N会读入一个东西但不是一个数。所以读入了N还要在判断一下。我菜啊，一开始不懂为啥这样，后来交了N次，又要来某位Ac过的大牛的代码又试了M次，终于明白了。此时本人通过率下降了2%，本题通过率下降了1%。
++++++++++++++++囧囧的分割线++++++++++++++++++
楼上说我说错了。。。大家当我啥都没说……
朱广恩
LV 6
@ 2016-11-12 21:38:00
