B. Luxurious Houses
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
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).
Input
The first line of the input contains a single number n (1 ≤ n ≤ 105) – the number of houses in the capital of Berland.
The second line contains n space-separated positive integers h__i (1 ≤ h__i ≤ 109), where h__i equals the number of floors in the i-th house.
Output
Print n integers _a_1, _a_2, …, a__n, where number a__i is the number of floors that need to be added to the house number i to make it luxurious. If the house is already luxurious and nothing needs to be added to it, then a__i should be equal to zero.
All houses are numbered from left to right, starting from one.
Sample test(s)
input
5
1 2 3 1 2
output
3 2 0 2 0
input
4
3 2 1 4
output
2 3 4 0
从后往前扫．． 更新最大值．
代码实现
1/*************************************************************************
2 > File Name: code/cf/#322/B.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年09月29日 星期二 00时27分25秒
6 ************************************************************************/
7
8#include<iostream>
9#include<iomanip>
10#include<cstdio>
11#include<algorithm>
12#include<cmath>
13#include<cstring>
14#include<string>
15#include<map>
16#include<set>
17#include<queue>
18#include<vector>
19#include<stack>
20#include<cctype>
21#define y1 hust111qqz
22#define yn hez111qqz
23#define j1 cute111qqz
24#define ms(a,x) memset(a,x,sizeof(a))
25#define lr dying111qqz
26using namespace std;
27#define For(i, n) for (int i=0;i<int(n);++i)
28typedef long long LL;
29typedef double DB;
30const int inf = 0x3f3f3f3f;
31const int N=1E5+7;
32int a[N];
33int ans[N];
34int n;
35int main()
36{
37 #ifndef ONLINE_JUDGE
38// freopen("in.txt","r",stdin);
39 #endif
40 cin>>n;
41 for ( int i = 1 ; i <= n ; i++)
42 scanf("%d",&a[i]);
43 int mx ;
44 ms(ans,0);
45 mx = a[n];
46 for ( int i = n-1 ; i >= 1 ; i--)
47 {
48 if (a[i]>mx)
49 {
50 mx = a[i];
51 continue;
52 }
53 else
54 {
55 ans[i] = mx-a[i]+1;
56 }
57 }
58 for ( int i = 1 ; i < n ; i++)
59 printf("%d ",ans[i]);
60 printf("%d",0);
61
62 #ifndef ONLINE_JUDGE
63 fclose(stdin);
64 #endif
65 return 0;
66}