A32891. 房屋积水程序文件名：t3.cpp输入文件名：t3.in输出文件名：t3.out。乌龟家的屋顶是凹凸不平的，所以每次雨后都会积水。为了知道屋顶是否会在暴雨后塌掉，他把屋顶的形状给了你，希望你帮他计算暴雨后屋顶的积水总量。乌龟的屋顶由顺次排在同一水平线上的n 个宽度为1、高度为整数(分别给出) 的瓦片组成。例如给定n = 5，瓦片的高度分别为4, 2, 3, 5, 1，屋顶可以画在下图所示的网格中，…
题目描述
房屋积水
程序文件名：t3.cpp
输入文件名：t3.in
输出文件名：t3.out。
乌龟家的屋顶是凹凸不平的，所以每次雨后都会积水。为了知道屋顶是否会在暴雨后塌掉，他把屋顶的形状给了你，希望你帮他计算暴雨后屋顶的积水总量。
乌龟的屋顶由顺次排在同一水平线上的n 个宽度为1、高度为整数(分别给出) 的瓦片组成。例如给定n = 5，瓦片的高度分别为4, 2, 3, 5, 1，屋顶可以画在下图所示的网格中，灰色格子为瓦片。
暴雨过后，如果一个方格向左右两侧延伸都能到达瓦片占据的方格，它就会积水。所以图中波浪线格子在暴雨后会积水，屋顶的积水方格总数为3。
输入
两个整数n, R1，表示屋顶的宽度和生成数列的首项。从左向右数第i (1 <= i <= n)个瓦片的高度ai = Ri mod 10
输出
一个整数，表示暴雨后屋顶积水方格的总数
样例输入
10 1
样例输出
23
数据规模
1<=n<=100
参考答案
#include<bits/stdc++.h>
using namespace std;
int a[1010],r[1010],dp[110][110];
int n,ans,ma;
void init()
{
cin>>n>>r[1];
for(int i=1;i<=n;++i){
a[i]=r[i]%10;
r[i+1]=(r[i]*6807+2831)%201701;
}
}
int check(int x)
{
int le,ri,i;
for(i=1;i<=n;++i)
if(a[i]>=x){le=i;break;}
for(i=n;i>=1;--i)
if(a[i]>=x){ri=i;break;}
for(i=le+1;i<=ri-1;++i)
if(a[i]<x)ans++;
}
int main()
{
init();
for(int i=0;i<=9;++i)
check(i);
cout<<ans;
return 0;
}答案解析
方法二：O(n^2)
#include<bits/stdc++.h>
using namespace std;
int a[1010],r[1010];
int n,ans,tot;
void init()
{
cin>>n>>r[1];
for(int i=1;i<=n;++i){
a[i]=r[i]%10;
r[i+1]=(r[i]*6807+2831)%201701;
}
}
int check(int x)
{
int max1=0,max2=0,minn;
for(int i=1;i<=x-1;++i)
max1=max(max1,a[i]);
for(int i=x+1;i<=n;++i)
max2=max(max2,a[i]);
minn=min(max1,max2);
if(minn>a[x])return minn-a[x];
else return 0;
}
int main()
{
freopen("t3.in","r",stdin);
freopen("t3.out","w",stdout);
init();
for(int i=2;i<=n-1;++i){
ans+=check(i);
}
cout<<ans;
fclose(stdin);fclose(stdout);
return 0;
}
方法三：O(n)
#include<bits/stdc++.h>
using namespace std;
int a[1010],r[1010],dp[110][110];
int n,ans,tot,ma;
void init()
{
cin>>n>>r[1];
for(int i=1;i<=n;++i){
a[i]=r[i]%10;
r[i+1]=(r[i]*6807+2831)%201701;
}
}
void pre()
{
ma=a[1];
for(int i=2;i<=n;++i){
le[i]=ma;
ma=max(ma,a[i]);
}
ma=a[n];
for(int i=n-1;i>=1;--i){
ri[i]=ma;
ma=max(ma,a[i]);
}
}
int main()
{
init();
pre();
for(int i=2;i<=n-1;++i){
ma=min(le[i],ri[i]);
if(ma>a[i])ans+=(ma-a[i]);
}
cout<<ans;
return 0;
}