hdu 5248 序列变换（二分枚举）-白红宇

hdu 5248 序列变换（二分枚举）

阅读量：4501 次

发布时间：2019-06-08

本文共 1254 字，大约阅读时间需要 4 分钟。

Problem Description

给定序列A={A1,A2,...,An}, 要求改变序列A中的某些元素，形成一个严格单调的序列B（严格单调的定义为：Bi

Input

第一行为测试的组数T(1≤T≤10).对于每一组：第一行为序列A的长度N(1≤N≤105)，第二行包含N个数，A1,A2,...,An.序列A中的每个元素的值是正整数且不超过106。

Output

对于每一个测试样例，输出两行：第一行输出："Case #i:"。i代表第 i 组测试数据。第二行输出一个正整数，代表满足条件的最小代价。

Sample Input

221 1032 5 4

Sample Output

Case #1: 0Case #2: 1

Source

二分枚举最小的代价。从后往前枚举判断序列是否为单调递减

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 using namespace std; 9 #define N 10000610 #define inf 1<<3011 int n;12 int a[N];13 bool solve(int mid){14 int tmp=a[n]+mid;15 for(int i=n-1;i>=1;i--){16 if(abs(tmp-1-a[i])<=mid){17 tmp=tmp-1;18 }19 else if(tmp-1>=a[i]){20 tmp=a[i]+mid;21 }22 else{23 return false; 24 }25 }26 return true;27 }28 int main()29 {30 int ac=0;31 int t;32 scanf("%d",&t);33 while(t--){34 scanf("%d",&n);35 for(int i=1;i<=n;i++){36 scanf("%d",&a[i]);37 }38 int low=0;39 int high=inf;40 while(low
             
              >1;42 if(solve(mid)){43 high=mid;44 }45 else{46 low=mid+1;47 }48 }49 printf("Case #%d:\n",++ac);50 printf("%d\n",low);51 52 }53 return 0;54 }