题目描述
乌龟家的屋顶是凹凸不平的，所以每次雨后都会积水。为了知道屋顶是否会在暴雨后塌掉，他把屋顶的形 状给了你，希望你帮他计算暴雨后屋顶的积水总量。
乌龟的屋顶由顺次排在同一水平线上的 n 个宽度为 1、高度为整数 (分别给出) 的瓦片组成。例如给定n = 5，瓦片的高度分别为 4, 2, 3, 5, 1，屋顶可以画在下图所示的网格中，灰色格子为瓦片。
暴雨过后，如果一个方格向左右两侧延伸都能到达瓦片占据的方格，它就会积水。所以图中波浪线格子在暴雨后会积水，屋顶的积水方格总数为 3。
输入
两个整数 n, R1，表示屋顶的宽度和生成数列的首项。从左向右数第 i (1<=i<=n)个瓦片的高度 ai = Ri mod 10
试题中使用的生成数列 R 定义如下：整数 0 ≤ R1 < 201701 在输入中给出。对于 i > 1，Ri = (Ri−1 × 6807 + 2831) mod 201701。
输出
一个整数，表示暴雨后屋顶积水方格的总数
样例输入
复制样例数据
10 1 样例输出
23
提示
数据规模 1 ≤ n ≤ 100
这题元旦时做的，但感觉这题思路挺好，存下来当作练习思维吧
题解思路：这题主要考察是思维：
第一步：我们首先考虑第一个元素，如果n==1，是没有可能的，也就是0，形不成闭合区间。
第二步：既然形不成闭合区间是0，那么绝对要有三个及三个以上的高度才有可能形成区间，也只是有可能比如说 5 4 3 2 1就不可以。
第三步：怎么确定至少三个区间，在这里如果要形成闭合区间，绝对在第i个数的前面，有一个数比i大，在i的后面也有一个数比i大。
第四步：因为要算出最大的积水面积，所以应该取i前面最大的数，与i后面最大的数，形成闭合区间，那么他能积多少水呢？两个最大值的最小值就是他能积的：
第五步：从第二个跑到第n-1个就行了，因为第一个前面没有元素，构不成积水面积，最后一个同理。
所以直接附上代码：
#include <stdio.h>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
typedef long long ll;
const int INF=1e9;
const int maxn=1e6+5;
int a[maxn];
ll R[maxn];
int M1[maxn];
int M2[maxn];
int main()
{
ll sum=0,sum1=0,n,x,y,z;
//scanf("%lld",&n);
scanf("%lld%lld",&n,&R[1]);
for(int i=2;i<=n;i++)
R[i]=(R[i-1]*6807+2831)%201701;
for(int i=1;i<=n;i++)
a[i]=R[i]%10;
/*for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);*/
M1[1]=a[1];
for(int i=2;i<=n;i++)
M1[i]=max(M1[i-1],a[i]);
M2[n]=a[n];
for(int i=n-1;i>=1;i--)
M2[i]=max(M2[i+1],a[i]);
for(int i=2;i<=n-1;i++)
sum+=min(M2[i],M1[i])-a[i];
printf("%d\n",sum);
return 0;
}
祝大家一次AC！
以后要多多注意思维的转换，和分步思想。
京公网安备 11010502036488号