题目传送门:
P2234 [HNOI2002] 营业额统计 - 洛谷 (luogu.com.cn)
前言:
这道题的核心是计算公司每天营业额的最小波动值,并将这些最小波动值累加起来,总体来说极简。下面为你们详细讲解~
First-问题分析:
题目中给出了最小波动值的定义:一天的最小波动值 = min {∣该天以前某一天的营业额−该天营业额∣},并且特别说明第一天的最小波动值为第一天的营业额。我们需要根据每天的营业额,依次计算出每一天的最小波动值,最后将所有最小波动值求和。
#具体思路步骤:
1、数据结构选择:
为了能够快速找到与当前营业额最接近的前几天的营业额,我们需要一个能够高效进行查找和插入操作的操作结构。这里我们选择 set。 because set 是一个有序容器,它会自动对插入的元素进行排序,并且支持对数时间复杂度的查找和插入操作。
2、输入处理:
首先读取公司营业的总天数 ,这决定了我们处理的数据量。然后使用一个循环,依次读取每一天的营业额。
3、最小波动值计算:
1.1、第一天:根据题目规定,第一天没有之前的营业额可供对比,所以