每当下雨时,FJ的牧场都会进水。由于牧场地面高低不平,被水淹没的地方不是很统一,形成一些岛屿。 FJ的牧场可描述成一个一维的地形图,由N(1 <= N <= 100,000)个彼此相连的柱状的高度值组成。高度值为H(1)...H(n)。假定这个地形图的两端有两条无限高的墙围着。 当雨一直下时,地形图上最低的区域先被水淹没,形成一些不相邻的岛屿。一旦水面高度到达一个区域的高度,则认为这个区域被淹没。 算出当雨从开始下到最后所有岛屿沉入水中,最多时可形成多少个岛屿。 【输入文件】 第1行:1个整数N 第2..N+1行:每行一个整数,表示一个区域的高度H(i). (1 <= H(i) <= 1,000,000,000) 【输出文件】 第1行: 1个整数,表示最多时能看到的岛屿数 【输入样例 1】 8 3 5 2 3 1 4 2 3 【输出样例 1】 4 【数据范围】 对于15%的数据:1≤N≤20; 对于30%的数据:1≤N≤1,000; 对于60%的数据:1≤N≤100,000; 对于100%的数据:1≤N≤1,000,000;1≤Hi≤1,000,000,000;
时间: 2024-02-25 15:56:01 浏览: 128
数学建模下雨
这是一道比较经典的题目,可以使用贪心算法来解决。具体思路如下:
首先,我们需要将高度值按从低到高的顺序进行排序,这样我们就可以按顺序遍历高度值;
然后,我们需要用一个变量记录当前水位的高度,初始值为0;
接下来,我们可以从第一个高度值开始遍历,对于每个高度值,我们都需要判断它是否被当前水位淹没了。如果被淹没了,就跳过;如果没有被淹没,就将它作为一个新的岛屿的起点,同时将当前水位的高度设置为它的高度值。然后继续向后遍历,直到找到下一个没有被淹没的高度值。
最后,我们遍历完所有的高度值后,就可以得到最终的岛屿数目了。
下面是代码实现:
```python
n = int(input())
heights = sorted([int(input()) for i in range(n)])
water_level = 0
island_count = 0
for h in heights:
if h <= water_level:
continue
else:
island_count += 1
water_level = h
print(island_count)
```
这段代码首先读入高度值,然后按从低到高的顺序进行排序。接着,使用 for 循环遍历每个高度值,并根据上述思路进行判断和计算。最后输出岛屿数目即可。
希望能够帮助到你!
阅读全文