Codeforces Round #322 (Div. 2) B. Luxurious Houses

原题: http://codeforces.com/contest/581/problem/B

---

题目大意: 给n个数, 表示n层楼, 问从左向右, 加盖几层楼可以使得当前的楼比右边最高的楼还高.

---

分析:开始的时候直接写了一个O(n^2)的算法, i遍历每个楼, j遍历当前楼右边的楼找出最大. 后来超时了, 想想发现可以从右向左扫,记录一下max 如果当前楼比max矮, 则盖max-ary[i]+1层, 然后每次扫一个数都更新max.

public void solve(int testNumber, InputReader in, OutputWriter out) {
            int n = in.readInt();
            int[] ary = IOUtils.readIntArray(in, n);
            int max = 0;
            int[] result = new int[n];
            for (int i = ary.length - 1; i >= 0; i--) {
                if (ary[i] <= max)
                    result[i] = max - ary[i] + 1;
                max = Math.max(max, ary[i]);
            }
            for (int i : result)
                out.print(i + " ");
        }