题解 CF581B 【Luxurious Houses】

发表于 | 更新于 | 评论数： | 阅读次数：
本文字数： 741 | 阅读时长 ≈ 1 分钟

不难看出，题目要求的是每一个房子后面最高的房子与它的高度差$+1$，（如果比它矮输出$0$）

我们定义

  • $maxn[i]$表示第$i$到第$n$个房子高度的最大值（$n$为房子数）

  • $h[i]$表示第$i$个房子的高度

因为$maxn[i+1]$存放的已经是第$i+1$到第$n$个房子的最大值了，所以第$i$到第$n$个房子的最大值只要让当前房子的高度与$maxn[i+1]$进行比较即可

即$maxn[i]=max(h[i],maxn[i+1])$

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
int n;
int h[MAXN] , maxn[MAXN];
int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	for(int i = 1; i <= n; i ++)
	{
		cin >> h[i];
	}
	for(int i = n; i >= 2; i --)
	   maxn[i] = max(h[i] , maxn[i + 1]); //预处理最大值
	for(int i = 1; i <= n - 1; i ++)
	  cout << max(maxn[i + 1] - h[i] + 1 , 0) << " ";//如果没比它高要输出0！
	cout << 0;//最后一个后面已经没有房子了当然是0
	return 0;
}