序列变换

Time Limit: 20 Sec Memory Limit: 256 MB

题目连接

http://acdream.info/problem?pid=1752

Description

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:0Case #2:1

HINT

题意

题解：

二分答案之后，再check一下就好

代码：

//qscqesze#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define test freopen("test.txt","r",stdin) #define maxn 2000001#define mod 10007#define eps 1e-9int Num;char CH[20];const int inf=0x3f3f3f3f;const ll infll = 0x3f3f3f3f3f3f3f3fLL;inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){ if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}inline void P(int x){ Num=0;if(!x){putchar('0');puts("");return;} while(x>0)CH[++Num]=x%10,x/=10; while(Num)putchar(CH[Num--]+48); puts("");}//**************************************************************************************int a[maxn];int n;bool check(int v){ int now = -inf; for(int i = 0;i < n;i++){ if(now-a[i] > v)return false; now = max(now+1,a[i]-v+1); } return true;}int main(){ int T; int iCase = 0; scanf("%d",&T); while(T--){ iCase++; scanf("%d",&n); for(int i = 0;i < n;i++) scanf("%d",&a[i]); int l = 0, r = 2000000; int ans = r; while(l <= r){ int mid = (l+r)/2; if(check(mid)){ ans = mid; r = mid-1; } else l = mid+1; } printf("Case #%d:\n%d\n",iCase,ans); } return 0;}