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.