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，如需轉載請自行聯系原作者