NYOJ-958山谷（二)【模拟】

柔光的暖阳◎ 2022-08-14 04:56 117阅读 0赞

## 山谷（二） ##

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 2

描述

八百里伏牛山连绵不断，高低起伏。

学习过数山谷的个数之后，小明想知道这些山谷中最多能装多少水。

我们用竖直的矩形表示山的高度，如图：

![20131212181653_72101.jpg][]

我们用这样一种形式来表示上图的山：\[6 1 4 6 7 5 1 6 4\]，每个数字代表山的高度。

假如连日暴雨，爆发山洪，这些山之间的山谷能装多少水？

![20131212181215_51044.jpg][]

规定用单位1的方块来计算容积。所以，在上边的图中下标为1以左都会漏掉。下标8以右的也会漏掉。剩下的只有在1和4、5和8之间的山谷有水（即蓝色方块），容积是13。

输入

多组测试数据，第一行给出数据组数T。（T<15)  
对于每组测试数据：  
第一行给定一个整数N（0 < N <= 1000000)，表示山的个数  
第二行有N个正整数，第i个数 a\[i\] (0 < a\[i\] <= 1000000) 表示第i座山的高度

输出

每组数据输出一行，表示所有山谷能装水的总容积。

样例输入

1
    9
    6 1 4 6 7 5 1 6 4

样例输出

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #include<algorithm>
    using namespace std;
    int a[1001000];
    int main()
    {
    	int T;	
    	scanf("%d",&T);
    	while(T--)
    	{
    		int n;
    		int i,j,k;
    		scanf("%d",&n);
    		for(i=0;i<n;i++)
    		{
    			scanf("%d",&a[i]);
    		}
    		long long ans=0;
    		int zuobiao1;
    		int zuobiao2;
    		int cnm=1;
    		for(j=0;j<n-1;)
    		{
    			if(a[j]>a[j+1])
    			{
    				int max=0;
    				long long he=0;
    				int zuobiao;
    				for(k=j+1;k<n;k++)
    				{
    					if(a[j]-a[k]>0)
    					he+=a[j]-a[k];
    					if(a[j]-a[k]<=0)
    					{
    						zuobiao=k;
    						break;	
    					}	
    				}
    				if(k==n)
    				{
    					cnm=0;
    					zuobiao1=j;
    					zuobiao2=n-1;
    					break;
    				}
    				else
    				{
    					ans+=he;
    				}
    				j=zuobiao;
    			}
    			else
    			{
    				j++;
    			}	
    		}
    		if(cnm==0)
    		{
    			int p;
    			int k;
    			for(p=zuobiao2;p>zuobiao1;)
    			{
    				if(a[p]>a[p-1])
    				{
    					long long he1=0;
    					int zz;
    					int zuo;
    					for(k=p-1;k>=zuobiao1;k--)
    					{		
    						if(a[p]-a[k]>0)
    						{
    							he1+=a[p]-a[k];
    						}
    						if(a[p]-a[k]<=0)
    						{
    							zuo=k;
    							break;
    						}
    					}
    					ans+=he1;
    					p=zuo;
    				}
    				else
    				{
    					p--;
    				}
    			}
    		}
    		printf("%lld\n",ans);
    	}
    	return 0;
    }

[20131212181653_72101.jpg]: http://acm.nyist.net/JudgeOnline/admin/kind/attached/20131212181653_72101.jpg
[20131212181215_51044.jpg]: http://acm.nyist.net/JudgeOnline/admin/kind/attached/20131212181215_51044.jpg