NOJ上机系统 准备中……
三峡大坝管理局连续记录了 $$$n$$$ 天的水位数据。工程师计划在这 $$$n$$$ 天中选择水位较低的某一天关闭闸门，并在之后的另一天，水位升高后打开闸门，利用两者的水位差进行水力发电。
请计算单次操作能够获得的最大水位差。若所有情况都无法产生正差值，则输出 $$$0$$$。
第一行一个整数 $$$n$$$，表示记录的天数。题目保证， $$$1 \leq n \leq 10^5$$$。
接下来 $$$n$$$ 行，每行一个整数 $$$h_i$$$，表示第 $$$i$$$ 天的水位。题目保证， $$$1 \leq h_i \leq 10^9$$$。
输出一个整数，表示最大可能的水位差。若不存在有效方案，输出 $$$0$$$。
6 7 1 4 3 6 5
5
3 3 2 1
0
对于第一组数据，可以选择第 $$$2$$$ 天蓄水，第 $$$5$$$ 天放水，此时水位差为 $$$6 - 1 = 5$$$。
对于第二组数据，无论如何放水，都无法产生正差值，因此输出 $$$0$$$。
题目保证，对于 $$$20\%$$$ 的数据，$$$n \leq 10$$$。
题目保证，对于 $$$40\%$$$ 的数据，$$$h_i$$$ 满足单调增或单调减。
题目保证，对于 $$$80\%$$$ 的数据，$$$n \leq 1000$$$。
题目保证，对于 $$$100\%$$$ 的数据，$$$1 \leq n \leq 10^5$$$，$$$1 \leq h_i \leq 10^9$$$。
信息
提供者 机考平台
代码 PROB1040
标签
提交 777
通过 313
通过率 40.28%
修改日期 2025-03-27 14:39:18
相关题目