c语言接雨水双指针课设
时间: 2023-07-13 10:07:31 浏览: 77
接雨水问题可以使用双指针来解决。首先我们可以分别记录左侧和右侧的最高高度,然后从左右两侧开始遍历,比较左右两侧的最高高度,如果左侧最高高度小于右侧最高高度,则从左侧开始遍历,否则从右侧开始遍历。遍历过程中,如果当前位置的高度小于等于左右两侧的最高高度中的较小值,则可以将当前位置的积水量计入答案中。
以下是一个使用双指针解决接雨水问题的C语言代码:
```c
#include <stdio.h>
#define MAXN 1005
int a[MAXN];
int left_max[MAXN], right_max[MAXN];
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}
left_max[0] = 0;
for (int i = 1; i <= n; i++)
{
left_max[i] = left_max[i - 1] > a[i] ? left_max[i - 1] : a[i];
}
right_max[n + 1] = 0;
for (int i = n; i >= 1; i--)
{
right_max[i] = right_max[i + 1] > a[i] ? right_max[i + 1] : a[i];
}
int ans = 0;
int l = 1, r = n;
while (l <= r)
{
if (left_max[l] < right_max[r])
{
ans += left_max[l] - a[l];
l++;
}
else
{
ans += right_max[r] - a[r];
r--;
}
}
printf("%d\n", ans);
return 0;
}
```
在该代码中,我们首先读入输入数据,并计算出左右两侧的最高高度。然后使用双指针遍历数组,计算积水量并累加到答案中,最后输出答案。
相关推荐
![md](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)