P3534 [POI2012]STU-Well

    • 63通过
    • 177提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 二分答案 POI 2012 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题意翻译

    给定一个非负整数序列A,每次操作可以选择一个数然后减掉1,要求进行不超过m次操作使得存在一个$A_k=0$且$\max(|x_i-x_{i-1}|)$最小,输出这个最小值以及此时最小的k

    题目描述

    Byteasar has set off on a journey along the Dry River, which crosses the Byteotian Desert.

    Unfortunately, the Dry River has dried out, and Byteasar has run out of water.

    His only hope is to dig a deep enough well in the dried river bed.

    Realising the graveness of his situation, Byteasar decides to plan everything carefully before he actually starts digging.

    The danger is that he drains his strength before he reaches the water level - in such case he is unlikely to survive.

    He managed to determine the depth of the water level. He also knows how much he can dig before losing strength.

    His only worry is a possible landslide, which might bury him alive.

    He sends you (via a satellite telephone) a topographic map of the river bed.

    And, of course, he asks you to help him determine where he should dig so that he reaches water before draining his strength while keeping the slope of his excavation as gentle as possible.

    He is waiting for your advice!

    输入输出格式

    输入格式:

    In the first line of the standard input two positive integers are given, $n$ and $m$ ($1\le n\le 1\ 000\ 000$, $1\le m\le 10^{18}$), separated by a single space.

    The second line holds $n$ positive integers $x_1,x_2,\cdots,x_n$ ($1\le x_i\le 10^9$), also separated by single spaces.

    Byteasar has enough energy to perform $m$ swings of the shovel.

    The numbers $x_1,x_2,\cdots,x_n$ describe the topography of the Dry River's bed.

    They represent the depth of the sand layer above the ground water level in successive one meter spaced spots along the river bed.

    With a single swing of the shovel Byteasar can extract an amount of the sand that decreases any of the numbers $x_i$ by 1.If any of these numbers, say $x_k$, drops to 0, this means that Byteasar has dug down to the water. But Byteasar has a secondary goal as well. He wants the following number $z$, characterising the slope of the sand hill, minimised:

    $z=max_{i=1,2,\cdots,n-1}|x_i-x_{i+1}|$ If there are multiple correct values of the number $k$,representing the spot where Byteasar is to dig down to reach the water, your program can pick one arbitrarily. The spots $1,2,\cdots,n$ are the only ones suitable for digging - elsewhere there is rock rather than sand. You may assume that Byteasar has enough energy to reach water at one of the spots.

    输出格式:

    Your program should print two integers to the standard output, separated by a single space:

    the spot $k$, where Byteasar should dig for water, and the minimum value of the number $z$.

    输入输出样例

    输入样例#1: 复制
    16 15
    8 7 6 5 5 5 5 5 6 6 7 8 9 7 5 5
    输出样例#1: 复制
    1 2
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。