HDU5248：序列變換（二分）

序列變換

Time Limit: 4000/2000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1348????Accepted Submission(s): 593

Problem Description

給定序列A={A1,A2,...,An}, 要求改變序列A中的某些元素，形成一個嚴格單調的序列B（嚴格單調的定義為：Bi<Bi+1,1≤i<N）。

我們定義從序列A到序列B變換的代價為cost(A,B)=max(|Ai?Bi|)(1≤i≤N)。

請求出滿足條件的最小代價。

注意，每個元素在變換前后都是整數。

Input

第一行為測試的組數T(1≤T≤10).

對于每一組：
第一行為序列A的長度N(1≤N≤105)，第二行包含N個數，A1,A2,...,An.
序列A中的每個元素的值是正整數且不超過106。

Output

對于每一個測試樣例，輸出兩行：

第一行輸出："Case #i:"。i代表第 i 組測試數據。

第二行輸出一個正整數，代表滿足條件的最小代價。

Sample Input

2 2 1 10 3 2 5 4

Sample Output

Case #1: 0 Case #2: 1

Source

2015年百度之星程序設計大賽 - 初賽(1)

思路：序列A每個數都不大于10^6，因此可以在0~10^6內二分出答案，判斷mid時可以正序或者倒序遍歷數組，下面代碼采用正序。

# include <stdio.h>
# include <stdlib.h>
int a[100001], n;
bool judge(int num)
{int x = a[0] - num, y;for(int i=1; i<n; ++i){y = a[i] - num;if(y <= x){y = x + 1;if(abs(y - a[i]) > num)return false;}x = y;}return true;
}int main()
{int t, cas = 1;scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=0; i<n; ++i)scanf("%d",&a[i]);int l=0, r=1000001, mid;while(l<r){mid = (l+r)>>1;if(judge(mid))r = mid;elsel = mid + 1;}printf("Case #%d:\n%d\n",cas++, r);}return 0;
}