题解 B3731 房屋积水

WsW_ · 2023-09-26 23:57:20 · 题解

思路

首先生成每个瓦片的高度。
对于每个瓦片，我们要求出该瓦片所在区域内水的高度。
先求假设以左边最高点为水的高度，会积多少水；再求假设以右边最高点为水的高度，会积多少水。两者较小值即为该瓦片上积的水，变量累计即可。

在循环的过程中，需要不断更新最高点。

代码和提交记录

#include<bits/stdc++.h>
using namespace std;

void change(int &r){
    r=(r*6807+2831)%201701;
}

int r,n,a[105];
int ans;
int lst;
int l[2][105];

int main(){
    scanf("%d%d",&n,&r);
    for(int i=1;i<=n;i++){
        a[i]=r%10;
        change(r);
    }
    for(int i=1;i<=n;i++){
        lst=max(lst,a[i]);
        l[0][i]=max(0,lst-a[i]);//以左边最高点为
    }
    lst=0;
    for(int i=n;i>0;i--){
        lst=max(lst,a[i]);
        l[1][i]=max(0,lst-a[i]);
    }
    for(int i=1;i<=n;i++)ans+=min(l[1][i],l[0][i]);
    printf("%d",ans);
    return 0;
}