
 63通过
 177提交
 题目提供者 洛谷
 评测方式 云端评测
 标签 二分答案 POI 2012 高性能
 难度 省选/NOI
 时空限制 1000ms / 128MB
最新讨论 显示
题意翻译
给定一个非负整数序列A，每次操作可以选择一个数然后减掉1，要求进行不超过m次操作使得存在一个$A_k=0$且$\max(x_ix_{i1})$最小，输出这个最小值以及此时最小的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,n1}x_ix_{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$.