1 /* 2     二分搜索：在0～1e6的范围找到最小的max (ai - bi)，也就是使得p + 1 <= a[i] + c or a[i] - c 3     比赛时以为是贪心，榨干智商也想不出来:( 4 */ 5 #include 
     
       6 #include 
      
        7 #include 
       
         8 #include 
        
          9 #include 
         
          10 using namespace std;11 12 const int MAXN = 1e5 + 10;13 const int INF = 0x3f3f3f3f;14 int a[MAXN];15 int n;16 17 bool check(int c)18 {19     int p = -1e6;20     for (int i=1; i<=n; ++i)21     {22         int now = max (p + 1, a[i] - c);23         if (now > a[i] + c)    return false;24         p = now;25     }26 27     return true;28 }29 30 int main(void)        //2015百度之星初赛1 1003 序列变换31 {32     int t, cas = 0;33     scanf ("%d", &t);34     while (t--)35     {36         scanf ("%d", &n);37         for (int i=1; i<=n; ++i)    scanf ("%d", &a[i]);38 39         int l = 0, r = 1e6;40         while (l < r)41         {42             int mid = (l + r) >> 1;43             if (check (mid))    r = mid;44             else    l = mid + 1;45         }46 47         printf ("Case #%d:\n", ++cas);48         printf ("%d\n", l);49     }50 51     return 0;52 }53 54 /*55 256 257 1 1058 359 2 5 460 */