Codeforces 1338A —— Powered Addition 题解

题目地址：https://codeforces.com/problemset/problem/1338/A

解题思路：对每一个元素 a，比较当前 a 和 在 a 之前的出现的最大值 Max，如果 a < Max，那么记录这个 diff 值，维护一个 MaxDiff。

如果 MaxDiff > 0，代表我们只需要 1 + 2 + 4 + .... + 2^(n-1) >= MaxDiff，即可达到使数组非递减的效果。

复杂度：时间：O(sum(ni) , 空间：O(1)

// AC: 546 ms 
// Memory: 2200 KB
// Array & DP: for every elements, find the max diff between current element and the former biggest element.
// Then try to add 1 + 2 + .. + 2^(n-1) to make diff reach, the answer is n.
// T:O(sum(ni)), S:O(1)
//  
import java.util.Scanner;

public class Codeforces_1338A_Powered_Addition {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int n = sc.nextInt(), curMax = Integer.MIN_VALUE, maxDiff = 0, ret = 0;
            for (int j = 0; j < n; j++) {
                int a = sc.nextInt();
                if (a > curMax) {
                    curMax = a;
                } else if (a < curMax) {
                    maxDiff = Math.max(maxDiff, curMax - a);
                }
            }
            if (maxDiff > 0) {
                int cur = 0, base = 0;
                while (cur < maxDiff) {
                    cur += Math.pow(2, base);
                    base++;
                }
                ret = base;
            }

            System.out.println(ret);
        }
    }
}