首页 > 其他 > 详细

洛谷 P1318 积水面积

时间:2017-12-23 18:17:56      阅读:249      评论:0      收藏:0      [点我收藏+]

题目描述

一组正整数,分别表示由正方体迭起的柱子的高度。若某高度值为x,表示由x个正立方的方块迭起(如下图,0<=x<=5000)。找出所有可能积水的地方(图中蓝色部分),统计它们可能积水的面积总和(计算的是图中的横截面积。一个立方体的位置,为一个单位面积)。

如图:柱子高度变化为 0 1 0 2 1 2 0 0 2 0

技术分享图片

图中蓝色部分为积水面积,共有6个单位面积积水。

输入输出格式

输入格式:

 

两行,第一行n,表示有n个数(3<=n<=10000)。第2行连续n个数表示依次由正方体迭起的高度,保证首尾为0。

 

输出格式:

 

一个数,可能积水的面积。

 

输入输出样例

输入样例#1: 复制
10
0 1 0 2 1 2 0 0 2 0
输出样例#1: 复制
6
思路:一层一层的从底下找。因为题目中说:“正立方的方块迭起。”,所以就不会出现一些特殊情况。
技术分享图片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int maxn,ans;
int num[10010];
int n,l,r,find;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&num[i]);
        maxn=max(maxn,num[i]);
    }
    for(int k=1;k<=maxn;k++){
        for(int i=2;i<=n-1;i++)
            if(num[i]>=k){ l=i;break; }
        for(int i=n-1;i>=2;i--)
            if(num[i]>=k){ r=i;break; }
        for(int i=l;i<r;i++)
            if(num[i]<k)    ans++; 
    }
    cout<<ans<<endl;
}

 

 

洛谷 P1318 积水面积

原文:http://www.cnblogs.com/cangT-Tlan/p/8093928.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!