2019深信服校招——木板接水
【2019深信服校招——木板接水】2019深信服校招——木板接水
题目描述
空地上竖立着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
#include
#include using namespace std;
void sub(vector &ivec, int &height)
{
for (auto &m : ivec)
m -= height;
}int getVolume(vector &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 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;
}
推荐阅读
- 2019-02-13——今天谈梦想（）
- 深入理解Go之generate
- 20190302|20190302 复盘翻盘
- 2019年12月24日
- 由浅入深理解AOP
- 2019.4.18感恩日记
- 2019.4.2咖啡冥想日记
- 2019-1-14
- 亲子日记（287）2019.4.27.
- 考前焦虑——接纳情绪，转移注意力