编程介的小学生 2016-12-16 08:39 采纳率: 20.5%
浏览 913
已采纳

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

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

  • 写回答

1条回答 默认 最新

  • threenewbee 2016-12-16 15:16
    关注

    http://blog.csdn.net/guard_mine/article/details/45748253

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题？

  • Sticks Problem
    2016-12-16 08:39
    回答 1 已采纳 http://blog.csdn.net/guard_mine/article/details/45748253
  • Sticks
    2017-09-13 00:47
    回答 1 已采纳 http://blog.csdn.net/qq_32426313/article/details/52083559
  • Magic Sticks
    2017-12-10 13:32
    回答 1 已采纳 https://blog.csdn.net/Baiyi_destroyer/article/details/81271213
  • Sticks Problem
    2019-10-07 13:35
    dianan0938的博客 Sticks Problem poj-2452 　题目大意：给你一串n个数的数列a，上面的数为a1到an。我们求最大的y-x，其中，y和x满足1.x<y 2.任意的x<i<y，都有ai>ax&&ai<ay。 　注释：n<=50000，ai<=...
  • Wooden_Sticks问题一直wrong，希望指出我程序错误的地方 c语言
    2021-03-08 23:09
    回答 2 已采纳 我找不出来哪里错了. c++做法, 用了一个sort排序(懒懒排序), 其他的用C语言也可以实现.希望这个代码能帮到你.  #include <cstdio> #include &l
  • Little Zu Chongzhi's Triangles golang 算法
    2017-10-30 15:05
    回答 1 已采纳 http://blog.csdn.net/Tc_To_Top/article/details/44003357
  • 这个问题如果不用多数组，还有什么别的方法，数组内存太多了，C语言 erlang golang r语言
    2018-12-22 00:44
    回答 1 已采纳 https://blog.csdn.net/Irish_Moonshine/article/details/78591089
  • poj 2452 Sticks Problem.md
    2021-11-17 05:37
    poj 2452 Sticks Problem.md
  • Just a Hook
    2017-08-17 01:53
    回答 2 已采纳 http://blog.csdn.net/acm_ted/article/details/7786749
  • Wool
    2017-10-29 08:33
    回答 1 已采纳 http://blog.csdn.net/liangzhaoyang1/article/details/51945069
  • POJ 2452 Sticks Problem
    2016-03-25 16:28
    Anthony_azy的博客 Sticks Problem Time Limit: 6000MS   Memory Limit: 65536K Total Submissions: 10282   Accepted: 2723 Description Xuanxuan has n sticks of different length. One day, ...
  • POJ2452_Sticks Problem
    2019-08-07 10:50
    风中之神111的博客 题意： 给你一组数a[n]，求满足a[i] < a[k] < a[j] (i <= k <= j)的最大的区间长度 j - i 解法1：O(n^2) 先记录每一位数A[i]后面连续大于这个数的长度len[i]，然后再这个长度里[i, i+len[i] )找最大的数...
  • Sticks Problem （单调队列）
    2017-08-12 21:23
    sdau20163940的博客 Sticks Problem Time Limit : 12000/6000ms (Java/Other) Memory Limit : 131072/65536K (Java/Other) Total Submission(s) : 31 Accepted Submission(s) : 6 Problem Description Xuanxuan has n sticks o
  • POJ_2452 Sticks Problem 【ST表 + 二分】
    2019-09-30 07:17
    weixin_30399155的博客 　Sticks Problem 二、分析 　对于$i$和$j$，并没有很好的方法能同时将他们两找到最优值，所以考虑固定左端点$i$。 　固定左端点后，根据题意，$a[i]$是最小值，那么现在的问题就转化成了求以$a[i]$为左端点...
  • poj2452——Sticks Problem
    2017-12-13 14:45
    tzyshiwolaogongya的博客 题目大意：给出n个数，找出Si为最小值Sj为最大值的子序列Si...Sj，求出所有这样的子序列中j-i的最大值 输入：（可以有很多case）  n (n  n个数（空格分隔） (not larger than 100000) ...
  • POJ 2452 Sticks Problem(二分+RMQ)
    2018-05-29 19:59
    Soar-的博客 题意：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 &lt;= k &lt;= n), ...
  • Sticks Problem--（单调队列）
    2017-08-14 21:30
    菜圾的博客 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 ), she finds that for some ...
  • poj 2452 Sticks Problem
    2019-08-23 10:10
    qq_34505594的博客 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), sh...
  • Sticks Problem POJ - 2452
    2018-09-13 12:21
    sunyutian1998的博客 http://poj.org/problem?id=2452 单调栈找出每个数a[i]右边第一个小于等于他的数在哪 记为pos[i] 然后在[i,pos[i]-1]内找一个最靠左的最大值在哪 记为p 则[i,p]即为所求 #include &lt;cstdio&gt; #...
  • poj-2452 Sticks Problem（二分+RMQ）
    2016-04-01 16:48
    acm_cxq的博客 Sticks Problem Time Limit: 6000MS   Memory Limit: 65536K Total Submissions: 10299   Accepted: 2729 Description Xuanxuan has n sticks of different length. One day, she put
  • 没有解决我的问题, 去提问

悬赏问题

  • ¥15 Attention is all you need 的代码运行
  • ¥15 一个服务器已经有一个系统了如果用usb再装一个系统，原来的系统会被覆盖掉吗
  • ¥15 使用esm_msa1_t12_100M_UR50S蛋白质语言模型进行零样本预测时，终端显示出了sequence handled的进度条，但是并不出结果就自动终止回到命令提示行了是怎么回事：
  • ¥15 前置放大电路与功率放大电路相连放大倍数出现问题
  • ¥30 关于<main>标签页面跳转的问题
  • ¥80 部署运行web自动化项目
  • ¥15 腾讯云如何建立同一个项目中物模型之间的联系
  • ¥30 VMware 云桌面水印如何添加
  • ¥15 用ns3仿真出5G核心网网元
  • ¥15 matlab答疑 关于海上风电的爬坡事件检测