PKU2452题解
发表时间：2010-05-26 21:09:19 浏览(2558) 评论(1)
PKU2452——Sticks Problem
【Description】
Xuanxuan has n sticks of different length. One day, she puts all her sticks in a line,
represented by S1, S2, S3, ...Sn. After measuring the length of each stick Sk (1 <= k <= n),
she finds that for some sticks Si and Sj (1<= i < j <= n), each stick placed between Si and
Sj is longer than Si but shorter than Sj.
Now given the length of S1, S2, S3, …Sn, you are required to find the maximum value j - i.
【Input】
The input contains multiple test cases. Each case contains two lines.
Line 1: a single integer n (n <= 50000), indicating the number of sticks.
Line 2: n different positive integers (not larger than 100000), indicating the length of each
stick in order.
【Output】
The maximum value j - i in a single line. If there is no such i and j, just output -1.
【Sample Input】
4
5 4 3 6
4
6 5 4 3
【Sample Output】
1
-1
【思路】
这道题我是用单调队列做的。
首先，倒着扫描N个长度，同时开一个单调队列。当当前长度比队尾的元素大时，更新队尾元素的DP值为队尾元素编号减去当前元素编号再减1，并弹出队尾元素。直到队列空或队尾元素大于当前元素。将该元素加入队尾。扫描完成后将队列中的剩余元素DP值赋成元素编号-1。这样，我们得到了DP数组。DP[i]表示i号元素前面连续有多少个元素长度小于i元素。
然后，正着扫描N个长度，同时开一个单调队列。当当前长度比队尾的元素小时，弹出队尾元素。将该元素加入队尾。这时，队列中所有元素的右侧直到当前元素之间的所有元素一定都比队列中的元素大（否则之前那个元素一定被弹出去了）。这时，以当前元素的DP值为依据二分队列中的元素。找到与当前元素距离不超过DP[当前元素]的最靠前的点，用这两点的距离更新答案。
复杂度O（t*NLogN）其中t为数据组数。
【代码】
var i,j,k,l,m,n,p,q,r,s,t,ans:longint;
a,queue,dp:array[0..500000] of longint;
procedure find_shorter_before;//找每个点前面有多少连续比它小的
begin
queue[1]:=n;p:=1;
for i:=n-1 downto 1 do
begin
while (p>0)and(a[queue[p]]<a[i]) do
begin
dp[queue[p]]:=queue[p]-i-1;
dec(p);
end;
inc(p);queue[p]:=i;
end;
for i:=1 to p do dp[queue[i]]:=queue[i]-1;
end;
procedure two_cut(x,y:longint);
var mid:longint;
begin
if (x>y) then exit;
mid:=(x+y) div 2;
if (i-queue[mid]<=dp[i]) then
begin
r:=i-queue[mid];
two_cut(x,mid-1);
end else two_cut(mid+1,y);
end;
procedure find_answer;//得到答案
begin
queue[1]:=1;p:=1;
for i:=2 to n do
begin
while (p>0)and(a[queue[p]]>a[i]) do dec(p);
inc(p);queue[p]:=i;
r:=0;
if (dp[i]>ans) then two_cut(1,p);
if (r>ans) then ans:=r;
end;
end;
begin
while not eof do
begin
read(n);
for i:=1 to n do read(a[i]);readln;
find_shorter_before;
ans:=0;
find_answer;
if (ans=0) then writeln(-1) else writeln(ans);
end;
end.
【难度】3
【总结】
想了好一会儿才想到的，编程水平下滑了。继续努力！
【Description】
Xuanxuan has n sticks of different length. One day, she puts all her sticks in a line,
represented by S1, S2, S3, ...Sn. After measuring the length of each stick Sk (1 <= k <= n),
she finds that for some sticks Si and Sj (1<= i < j <= n), each stick placed between Si and
Sj is longer than Si but shorter than Sj.
Now given the length of S1, S2, S3, …Sn, you are required to find the maximum value j - i.
【Input】
The input contains multiple test cases. Each case contains two lines.
Line 1: a single integer n (n <= 50000), indicating the number of sticks.
Line 2: n different positive integers (not larger than 100000), indicating the length of each
stick in order.
【Output】
The maximum value j - i in a single line. If there is no such i and j, just output -1.
【Sample Input】
4
5 4 3 6
4
6 5 4 3
【Sample Output】
1
-1
【思路】
这道题我是用单调队列做的。
首先，倒着扫描N个长度，同时开一个单调队列。当当前长度比队尾的元素大时，更新队尾元素的DP值为队尾元素编号减去当前元素编号再减1，并弹出队尾元素。直到队列空或队尾元素大于当前元素。将该元素加入队尾。扫描完成后将队列中的剩余元素DP值赋成元素编号-1。这样，我们得到了DP数组。DP[i]表示i号元素前面连续有多少个元素长度小于i元素。
然后，正着扫描N个长度，同时开一个单调队列。当当前长度比队尾的元素小时，弹出队尾元素。将该元素加入队尾。这时，队列中所有元素的右侧直到当前元素之间的所有元素一定都比队列中的元素大（否则之前那个元素一定被弹出去了）。这时，以当前元素的DP值为依据二分队列中的元素。找到与当前元素距离不超过DP[当前元素]的最靠前的点，用这两点的距离更新答案。
复杂度O（t*NLogN）其中t为数据组数。
【代码】
var i,j,k,l,m,n,p,q,r,s,t,ans:longint;
a,queue,dp:array[0..500000] of longint;
procedure find_shorter_before;//找每个点前面有多少连续比它小的
begin
queue[1]:=n;p:=1;
for i:=n-1 downto 1 do
begin
while (p>0)and(a[queue[p]]<a[i]) do
begin
dp[queue[p]]:=queue[p]-i-1;
dec(p);
end;
inc(p);queue[p]:=i;
end;
for i:=1 to p do dp[queue[i]]:=queue[i]-1;
end;
procedure two_cut(x,y:longint);
var mid:longint;
begin
if (x>y) then exit;
mid:=(x+y) div 2;
if (i-queue[mid]<=dp[i]) then
begin
r:=i-queue[mid];
two_cut(x,mid-1);
end else two_cut(mid+1,y);
end;
procedure find_answer;//得到答案
begin
queue[1]:=1;p:=1;
for i:=2 to n do
begin
while (p>0)and(a[queue[p]]>a[i]) do dec(p);
inc(p);queue[p]:=i;
r:=0;
if (dp[i]>ans) then two_cut(1,p);
if (r>ans) then ans:=r;
end;
end;
begin
while not eof do
begin
read(n);
for i:=1 to n do read(a[i]);readln;
find_shorter_before;
ans:=0;
find_answer;
if (ans=0) then writeln(-1) else writeln(ans);
end;
end.
【难度】3
【总结】
想了好一会儿才想到的，编程水平下滑了。继续努力！
网友评论：
 | 1 Guest 于 2010-06-02 15:50:57 说： | 回复 |
|---|---|---|
路过仰慕下。。。 |