题解 CF581B 【Luxurious Houses】

题目解析：

给你n栋房子，问你第i栋房子要再搭几层才能比它后面所有的房子高 （注意：是要严格大于，不能等于）

所以我们只要找到第i栋房子后面最高的一栋，然后比较

样例说明：

5

1 2 3 1 2

第1栋房子高度为1，身后最高的房子高度为3，需要增加3层才能才能大于身后所有房子，为3；

第2栋房子高度为2，身后最高的房子高度为3，需要增加2层才能才能大于身后所有房子，为2；

第3栋房子高度为3，身后最高的房子高度为2，自身已经高于身后最高的房子，不需要增加，为0；

第4栋房子高度为1，身后最高的房子高度为2，需要增加2层才能才能大于身后所有房子，为2；

第5栋房子高度为2，身后没有房子，所以不用增加，为0；

输出：

3 2 0 2 0

怎样来找出第i栋房子身后的最大值呢？

代码实现：

for(int i=n;i>=1;i--)    //注意，是从后往前
    maxn[i]=max(a[i],maxn[i+1]);    //处理最大值

原理：

让我们来直接模拟一下

2 1 3 2 1（注意：是从后往前）

最后一栋房子身后没有房子了，那他的最大值就是自己

maxn[i]=2

倒数第二栋：

前一栋的最大值和自己相比较

maxn[i]=(2,1)

maxn[i]=2

倒数第三栋：

maxn[i]=(2,3)

maxn[i]=3

倒数第四栋：

maxn[i]=(3,2)

maxn[i]=3

倒数第五栋：

maxn[i]=(3,1)

maxn[i]=3

结束！

那怎么来输出差多少层呢？

代码实现：

printf("%d ",max(maxn[i+1]-a[i]+1,0));    //因为可能会有自身本就高于身后房屋的情况，相减出现负数时要输出0

这段代码还是很好理解的吧！

接下来就是AC代码了！

#include <cstdio>
#include <algorithm>    //包涵max和min函数的头文件
using namespace std;
int a[100010],maxn[100010];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    for(int i=n;i>=1;i--)   //注意，是从后往前
        maxn[i]=max(a[i],maxn[i+1]);    //处理最大值
    for(int i=1;i<=n;i++)
        printf("%d ",max(maxn[i+1]-a[i]+1,0));  //因为可能会有自身本就高于身后房屋的情况，相减出现负数时要输出0
    return 0;
}