Sticks Problem
| Time Limit: 6000MS |
? |
Memory Limit: 65536K |
| Total Submissions: 10141 |
? |
Accepted: 2682 |
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 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的序列 其中 Si ~ Sj (1<= i < j <= n)为其子序列 问：满足Si ~ Sj 中任意一个数大于Si 且 小于Sj的序列中，j - i的值最大为多少。
解题思路： 一开始就没想过暴力，但是其实暴力是可以过的，坑。。。。。
然而我的方法是用RMQ处理出区间最值，然后暴力扫过去，对每一个数 用两次二分找出 这个数所能形成的最大区间。 （先假设起点为i）两次二分作用分别为：
第一次：找出i能作为最小值的最大区间位置（其实这个可以用单调栈来处理） 第二次：在第一次找出的区间内寻找出该区间最大值的位置
#include
#include
#include
#include
#include
#include
#include
#include
?
|