Fork () function return value problem

2023-01-10   ES  

The uneven ground always accumulates water when it rains. Assuming that the ground is one -dimensional, each width is 1, and the height is non -negative. Then you can use an array to express a piece of ground. For example, [0,1,0,2,1,1,1,3,2,1,2,1] can be used to indicate the floor of the figure below:

After the rain is over rain, the ground will accumulate water. The blue area in the picture above is the water accumulation area. Now give you an array to represent the ground, and how much water has the water accumulation of the ground after the rain (assuming that it does not evaporate and does not penetrate).

Input

The first line is an integer M, which means that there is a group M test sample, not more than 100.
The next M block, each line is a positive integer n, indicating the total width of the ground (array length), no more than 20,000.
The next line is N integer, which is separated by spaces, indicating the height of the ground.

Output

For the input of each group, an integer represents the water accumulation.

Sample Input

2
12
0 1 0 2 1 0 1 3 2 1 2 1
4
1 0 0 2

Sample Output

6
2

shortcoming effect

The amount of water depends on the height of the lower ground.

在这里插入图片描述
As shown in the figure, find the highest ground height on the left side of each column and the highest ground height on the right, find the minimum value of the two highest heights, and use the minimum value to minimize the current calculation column. The ground height, if the result is assigned after the decrease is reduced, the amount of water accumulation is not added, otherwise, add.

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[20010];
int left[20010],right[20010];
int main()
{
    
    int t;
    scanf("%d",&t);
    while(t--)
    {
    
        int n;
        scanf("%d",&n);
        for(int i=0; i<n; i++)
            scanf("%d",&a[i]);
        int max1=0;
        for(int i=0; i<n; i++)// Seek the largest on the left
        {
    
            left[i]=max1;
            if(a[i]>max1)
                max1=a[i];
        }
        int max2=0;
        for(int i=n-1; i>=0; i--)// Zi U is the largest on the right
        {
    
            right[i]=max2;
            if(a[i]>max2)
                max2=a[i];
        }
        int sum=0;
        for(int i=0; i<n; i++)
        {
    
            int x=min(right[i],left[i]);// Seek the minimum value on both sides
            if(x-a[i]>0)
                sum+=(x-a[i]);
        }
        printf("%d\n",sum);
    }
    return 0;
}

source

Related Posts

Right sidebar and return to the top right sidebar code SPONGEBOB

The functions between the two JS call each other

More than 5G and Hongmeng, the latest big move in Huawei, throw AI to calculate the nuclear bomb

linux process operation wakeme

Fork () function return value problem

Random Posts

Android error report summary (continuous update)

FreeMarker page static

NIO’s Sao Operation 1. FileChannelHouxinlin

Vue Sort the array obtained

Python decorative (@Wraps) and closure use examples in detail