您现在的位置是:首页 > 正文

北湖深坑题

2024-04-01 05:05:26阅读 2

题目信息

十年前,北湖还只是一个深坑,未完成蓄水工作。为了确保蓄水工作的顺利进行,我们需要对北湖的蓄水量进行粗略估计。
为了简化运算,我们假设北湖的地面是一维的,每一块宽度都为1,高度是非负整数,那么可以用一个数组来表达一块地面。
例如数组[0,1,0,2,1,0,1,3,2,1,2,1]可以用来表示下图地面:
在这里插入图片描述
图中绿色代表地面部分,蓝色部分代表蓄水部分,蓄水量为 6 。

输入

样例输入有多组。

第一行输入整数 T(1≤T≤100)表示有 T 组用例;

接下来,对于每组用例,输入一个正整数n(1≤n≤100000) ,表示地面总宽度为 n 。

接下来一行是 n 个数a ,用空格隔开,表示地面高度。(0≤a≤1e9)

输出

对于每个用例输出一行一个数字,表示蓄水总量。

测试样例

2
12
0 1 0 2 1 0 1 3 2 1 2 1
5
5 2 3 2 4
6
5

解答

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n;
        cin >> n;
        int arr[100010];
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &arr[i]);
        }
        long long water = 0;
        int leftLargest = 0, rightLargest = 0;
        int left[100010];
        //left 数组中保存每个元素左边的最大值,left[i],表示数组中第i个元素的左边最大值。
        int right[100010];
        //right数组中保存每个元素左边的最大值,right[i],表示数组中第i个元素的右边最大值。
        for (int i = 0; i < n; i++)
        {
            leftLargest = max(leftLargest, arr[i]);
            left[i] = leftLargest;
        }
        //先遍历一次找出每个元素左边最大值。
        for (int i = n - 1; i >= 0; i--)
        {
            rightLargest = max(rightLargest, arr[i]);
            right[i] = rightLargest;
        }
        //遍历找到每个元素右边最大值。
        for (int i = 0; i < n; i++)
        {
            water += min(left[i], right[i]) > arr[i] ? min(left[i], right[i]) - arr[i] : 0;
        }
        cout << water << endl;
    }
}

网站文章

  • linux上安装MySQL

    linux上安装MySQL

    linux上原有mysql卸载,安装mysql过程及遇到的问题和解决方法 一、前期准备 二、安装MySQL 三、遇到的问题

    2024-04-01 05:05:17
  • 安装moviepy库报错

    安装moviepy库报错

    由于已经存在这个库,因此在尝试使用pip进行安装时,会显示&quot;Found existing installation&quot;的信息,而不会重新安装。根据您提供的错误信息,&quot;Inv...

    2024-04-01 05:04:38
  • thymeleaf 添加页面隐藏值

    切记切记这样写是不对的: ...

    2024-04-01 05:04:30
  • 计算机辅助教学时必不可少的,浅谈计算机辅助教学在中学语文教学中的应用

    计算机辅助教学时必不可少的,浅谈计算机辅助教学在中学语文教学中的应用

    论文导读:在有了计算机网络及多媒体设施,情势便发生了很大改变。比如在讲授《再别康桥》这一课时,可以在课件中插入由濮存昕朗诵的《再别康桥》的录音。学生在听录音的时候,远比老师朗诵时要认真、专注许多。而且...

    2024-04-01 05:04:23
  • 【数学基础】线性方程组解情况整理

    【数学基础】线性方程组解情况整理

    一、非齐次线性方程组,无解,多解,唯一解 非齐次线性方程组,就是方程组的等式右边不为0的方程组,系数加上方程等式右边的矩阵,叫做增广矩阵。 【例1】求解下列线性方程组 化简后的有效方程组个数小于未知数个数,有多个解。 第一步,先列出增广矩阵: 第二步,用高斯消元法化简,化简成阶梯矩阵 先把第2行换到第1行 第2行减第1行的2倍,第3行减第1行的3倍,得到 第3行减...

    2024-04-01 05:03:44
  • 切换域名后,ssh配置问题

    OS:CentOS release 6.10 (Final)问题:今天在在gp迁移测试时,把GP备份的域名从A机迁移到了B机。配置后,发现使用ssh 命令登录到需要同步文件到GP备机时,发现失败,提示信息如下:@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@The RSA host key for gp69.d...

    2024-04-01 05:03:36
  • 全球WIFI功率(信号)最强的国家清单,无线WIFI调优

    全球WIFI功率(信号)最强的国家清单,无线WIFI调优

    全球无线wifi信号最强的国家,无线调优

    2024-04-01 05:03:28
  • 医学图象分割常用损失函数(附Pytorch和Keras代码)

    医学图象分割常用损失函数(附Pytorch和Keras代码)

    汇总了医学图象分割常见损失函数,包括Pytorch代码和Keras代码,部分代码也有运行结果图!

    2024-04-01 05:03:21
  • LLMs之Falcon:《The RefinedWeb Dataset for Falcon LLM: Outperforming Curated Corpora with Web Data, and

    LLMs之Falcon:《The RefinedWeb Dataset for Falcon LLM: Outperforming Curated Corpora with Web Data, and...

    2024-04-01 05:02:41
  • UVALive - 3938 &quot;Ray, Pass me the dishes!&quot; 线段树

    题目大意:给你一个N个数字的序列和M个问题,问题的内容是给出一个区间[x,y],然后求出这个区间的满足x 解题思路:这题的线段树比较复杂,以前的线段树只维护一个值而已,现在的线段树维护的是三个值,前缀和pre,连续和sub,后缀和suf,要求区间[x,y]的满足条件的a,b无非有三种情况,假设现在的区间时的[l,r],他的两个子区间分别为,左子区间[l,mid],右子区间[mid+1,r]

    2024-04-01 05:02:31