J - 序列變換---沒找到原題----【貪心+二分】

J - 序列變換

Time Limit:2000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Submit

Status

Description

給定序列A = \{A_1, A_2,...,A_n\}, 要求改變序列A中的某些元素，形成一個嚴格單調的序列B（嚴格單調的定義為：B_i < B_{i+1}, 1 \leq i < N）。 

我們定義從序列A到序列B變換的代價為cost(A, B) = max(|A_i - B_i|) (1 \leq i \leq N)。 

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

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

Input

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

對于每一組： 

第一行為序列A的長度N(1 \leq N \leq 10^5)，第二行包含N個數，A_1, A_2, ...,A_n. 

序列A中的每個元素的值是正整數且不超過10^6。

Output

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

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

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

Sample Input

2

2

1 10

3

2 5 4 

Sample Output

Case #1:

Case #2:

1 

每次用二分判斷在最大差為M時，是否可以形成單調遞增的序列，，

在M的情況下，在shu[ i ] 時，我們要盡力使shu [ i ] 小，，即盡量使shu [ i ] 為( 靠近 )shu [ i - 1 ]+ 1,

這樣當shu [ i ] 小于 shu [ i-1] ,他們的差才會盡可能的小，，，最大可能不超過M，，，，， 

沒仔細看，，以為  

hdoj 5256   和這題一樣，，在杭電上一交就wrong了。。。。感覺這題是那個的變型，，，，杭電這個難一些。。。

以後要把它ＡＣ了。。

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,shu[110000],hou[110000];
int M,R,L,ans;
int zhao(int xx)
{
//	printf("%d     999\n",xx);
//	bool cha=false;
	bool fafe=true;
	hou[1]=shu[1]-xx;
//	if (xx==0)
//	cha=true;
//	if (cha) printf("%d  11111        ",shu[1]);
	for (int i=2;i<=n;i++)
	{
		hou[i]=shu[i];
		if (hou[i]>hou[i-1])
		{
			if (hou[i]-hou[i-1]-1>xx)
			{
				hou[i]=hou[i]-xx;
			}
			else
			hou[i]=hou[i-1]+1;
		}
		else
		{
			if (hou[i-1]+1-hou[i]<=xx)
			hou[i]=hou[i-1]+1;
			else
			{
				fafe=false;
				break;
			}
		}
//		if (cha) printf("%d %d  ",i,shu[i]);
	}
//	if (cha) printf("   6666\n");
	return fafe;
}
int main()
{
	int t;scanf("%d",&t);
	for (int ca=1;ca<=t;ca++)
	{
		scanf("%d",&n);
		for (int i=1;i<=n;i++)
		scanf("%d",&shu[i]);
		printf("Case #%d:\n",ca);
		bool kp=true;
		{
			for (int i=1;i<n;i++)
			if (shu[i]>=shu[i+1])
			{
				kp=false;
				break;
			}
		}
		if (kp)
		{
			printf("0\n");continue;
		}
		L=0;R=1e6+100;
		while (R>=L)
		{
			M=(L+R)/2;
			if (zhao(M))
			{
				
				ans=M;
				R=M-1;
//				printf("%d   guo\n",ans);
			}
			else
			L=M+1;
		}
		printf("%d\n",ans);
	}
	return 0;
}