Codeforces Round #322 (Div. 2) B. Luxurious Houses | 书脊
http://codeforces.com/contest/581/problem/B
分析:开始的时候直接写了一个O(n^2)的算法, i遍历每个楼, j遍历当前楼右边的楼找出最大. 后来超时了, 想想发现可以从右向左扫,记录一下max 如果当前楼比max矮, 则盖max-ary[i]+1层, 然后每次扫一个数都更新max.
Read full article from Codeforces Round #322 (Div. 2) B. Luxurious Houses | 书脊
http://codeforces.com/contest/581/problem/B
The capital of Berland has n multifloor buildings. The architect who built up the capital was very creative, so all the houses were built in one row.
Let's enumerate all the houses from left to right, starting with one. A house is considered to be luxurious if the number of floors in it is strictly greater than in all the houses with larger numbers. In other words, a house is luxurious if the number of floors in it is strictly greater than in all the houses, which are located to the right from it. In this task it is assumed that the heights of floors in the houses are the same.
The new architect is interested in n questions, i-th of them is about the following: "how many floors should be added to the i-th house to make it luxurious?" (for all i from 1 to n, inclusive). You need to help him cope with this task.
Note that all these questions are independent from each other — the answer to the question for house i does not affect other answers (i.e., the floors to the houses are not actually added).
题目大意: 给n个数, 表示n层楼, 问从左向右, 加盖几层楼可以使得当前的楼比右边最高的楼还高.分析:开始的时候直接写了一个O(n^2)的算法, i遍历每个楼, j遍历当前楼右边的楼找出最大. 后来超时了, 想想发现可以从右向左扫,记录一下max 如果当前楼比max矮, 则盖max-ary[i]+1层, 然后每次扫一个数都更新max.
3
4
5
6
7
8
9
10
11
12
13
|
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 + " ");
}
|
