首页 > 代码库 > 水池问题
水池问题
看下面这个图片
在这个图片里我们有不同高度的墙。这个图片由一个整数数组所代表，数组中每个数是墙的高度。上边的图可以表示为数组[2,5,1,2,3,4,7,7,6], 假如开始下雨了，那么墙之间的水坑能够装多少水呢？
解法:
1.第一轮循环:从左到右, 找到依次递增的最大的数字A, 然后继续向右, 找到最后一个不大于A的数字B, 计算数字A和数字B之间的水量, 然后重复上述步骤;
2.第二轮循环:从右到左, 重复上述步骤;
1 #include <iostream> 2 using namespace std; 3 4 int Volume(int* vArr, int vSize); 5 int Cal(int* vArr, int vLeft, int vRight); 6 7 int Volume(int* vArr, int vSize) 8 { 9 int lLeft, lRight, rLeft, rRight;10 int nValue = http://www.mamicode.com/0;11 int i, j;12 13 14 for (i = 0; i < vSize - 1; ++i)15 {16 if (vArr[i] <= vArr[i + 1])17 {18 continue;19 }20 lLeft = i;21 for (j = lLeft + 1; j < vSize; ++j)22 {23 if (vArr[j] <= vArr[lLeft])24 {25 continue;26 }27 lRight = j;28 nValue += Cal(vArr, lLeft, lRight);29 break;30 }31 if ( j != vSize )32 {33 i = lRight - 1;34 }35 else36 {37 break;38 }39 }40 41 42 for (i = vSize - 1; i > 0; --i)43 {44 if (vArr[i] <= vArr[i - 1])45 {46 continue;47 }48 rRight = i;49 for (j = rRight - 1; j >= 0; --j)50 {51 if (vArr[j] <= vArr[rRight])52 {53 continue;54 }55 rLeft = j;56 nValue += Cal(vArr, rLeft, rRight);57 break;58 }59 if ( j != 0 )60 {61 i = rLeft + 1;62 }63 else64 {65 break;66 }67 }68 69 return nValue;70 }71 72 int Cal(int* vArr, int vLeft, int vRight)73 {74 int nMin;75 int nValue = http://www.mamicode.com/0;76 int tmp;77 78 nMin = (vArr[vLeft] < vArr[vRight]) ? vArr[vLeft] : vArr[vRight];79 for (int i = vLeft; i < vRight; ++i)80 {81 tmp = nMin - vArr[i];82 if ( tmp > 0 )83 nValue += tmp ;84 }85 86 return nValue;87 }88 89 90 int main()91 {92 int arr[] = {2,5,1,3,1,2,1,7,7,6};93 94 cout << Volume(arr, sizeof(arr) / sizeof(int)) << endl;95 return 0;96 }
水池问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。