BC 2015在百度之星程序设计大赛 - 预赛(1)(系列转换-二分法答案贪婪)系列转换

Accepts: 816

Submissions: 3578

Time Limit: 4000/2000 MS (Java/Others)

Memory Limit: 32768/32768 K (Java/Others)

Problem Description

给定序列A={A 1 ,A 2 ,...,A n } , 要求改变序列A中的某些元素，形成一个严格单调的序列B（严格单调的定义为：B i <B i+1 ,1≤i<N ）。

我们定义从序列A到序列B变换的代价为cost(A,B)=max(|A i −B i |)(1≤i≤N) 。

请求出满足条件的最小代价。

注意，每一个元素在变换前后都是整数。

Input

第一行为測试的组数T(1≤T≤10) .

对于每一组： 第一行为序列A的长度N(1≤N≤10 5 ) ，第二行包括N个数，A 1 ,A 2 ,...,A n  . 序列A中的每一个元素的值是正整数且不超过10 6  。

Output

对于每个測试例子，输出两行：

第一行输出："Case #i:"。

i代表第 i 组測试数据。

第二行输出一个正整数，代表满足条件的最小代价。

Sample Input

Sample Output

<a target="_blank" href="http://bestcoder.hdu.edu.cn/contests/contest_statistic.php?cid=600&amp;pid=1003"></a>

二分答案，每一个数贪最小

版权声明：本文博主原创文章，博客，未经同意不得转载。

本文转自mfrbuaa博客园博客，原文链接：http://www.cnblogs.com/mfrbuaa/p/4909389.html，如需转载请自行联系原作者