自动搬运

查看原文

来自洛谷，原作者为

	WsW_ 欢迎入群872763867||题解求赞！题解看不懂请私信

搬运于2025-08-24 21:14:41，当前版本为作者最后更新于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;
}