2019深信服校招笔试题------木板接水

2019深信服校招笔试题——木板接水

详细答案见链接:https://blog.csdn.net/lizhentao0707/article/details/82828338

题目:

空地上竖立着n个从左到右排列的木板,它们可以把水挡住,但溢出最边上木板的水将会流到空地上。已知木板间距都是单位1,现给定每个木板的高度,请求出总共能接住的水量?说明一点,这里只考虑间距(宽度)和高度,不考虑第三个维度,因此水量是平方单位。

示例1,木板高度分别是2,1,3,那么我们可以接住2*2=4平方单位的水,如下图所示。注意,中间那个木板被水淹没了。

示例2,木板高度分别是2,4,3,那么可以接住2*1+3*1=5平方单位的水,如下图所示。


思路:不断降低所有木板高度 (如图)

(1) 先找到左右两端木板高度的较小值minHeight=min(ivec[0],ivec[size-1]) (ivec中存放排列的木板高度),求出这部分容量volume=(size-1)*miniHeight;

(2) 将所有木板长度减去minHeight,得到新的排列木板序列,定义两个指针low、high,分别从左右开始遍历数组ivec,找到左右两端第一个高度大于0的木板,此时minHeight=min(ivec[low],ivec[high]), volume=(high-low)*minHeight;故总共能接住的总量sum += volume;(每次容量相加)

(3) 重复步骤2,直至木板序列中只有一块木板高度大于0或全部木板高度均小于0,则此时sum为最大容量。


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void sub(vector<int> &ivec, int &height)
{
    for (auto &m : ivec)
        m -= height;
}

int getVolume(vector<int> &ivec, int &low, int &high, int &height)
{
    int size = ivec.size();
    int volume = 0;
    for (; low < size; low++)
    {
        if (ivec[low]>0)
            break;
    }
    for (; high >= 0; high--)
    {
        if (ivec[high]>0)
            break;
    }
    if (low < size && high < size)
    {
        height = min(ivec[high], ivec[low]);
        volume = (high - low)*height;
    }
    return volume;
}

int main()
{
    int t;
    cin >> t; 
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> ivec(n, 0);
        for (auto &m : ivec)
            cin >> m;
        int sum = 0;
        int size = ivec.size();
        int low = 0; 
        int high = size - 1;
        int height = min(ivec[low], ivec[high]);
        int volume = getVolume(ivec, low, high, height);
        while (low < size && high < size && ivec[low] > 0 && ivec[high] > 0)
        {
            sum += volume;
            sub(ivec, height);
            volume = getVolume(ivec, low, high, height);
        }
        cout << sum << endl;
    }
    return 0;
}
#笔试题目##校招##深信服#
全部评论
找到最高的木板mh,从第1块木板到mh,找一个非降序列(遇到比当前最大值小的位置,就用最大值填充),从第n块木板到mh,找一个非降序列(遇到比当前最大值小的位置,就用最大值填充)。最后计算序列上相邻的木板可以装多少水就可以 例如1,3,2,4,2,3,1 可以得到序列1,3,3,4,3,3,1 可以装1+3+3+3+3+1的水
3 回复
分享
发布于 2018-09-24 22:18
和你想法一样,实现有点不同: #include <stdio.h> #define N 100005 int main(void) { int t; scanf("%d", &t); while (t--) { int i, n, num[N]; scanf("%d", &n); for (i = 0; i < n; i++) scanf("%d", num + i); int left = 0, right = n - 1, res = 0, counted = 0; while (right > left) { int min = num[left] < num[right] ? num[left] : num[right]; if (min > counted) { res += (min - counted) * (right - left); counted = min; } if (num[left] < num[right]) left++; else right--; } printf("%d\n", res); } return 0; }
3 回复
分享
发布于 2018-09-24 22:40
乐元素
校招火热招聘中
官网直投

相关推荐

4 19 评论
分享
牛客网
牛客企业服务