这是一个创建于 1658 天前的主题，其中的信息可能已经有所发展或是发生改变。
某雪场共有 N 座雪山，数组 altitude 中存储了各雪山海拔（精确到整数）。雪场出售新手票与老手票，新手区票价较高。 若该雪场内最高海拔与最低海拔的差值大于 difference，则为老手区；否则为新手区。现在是滑雪活动旺季，雪场经营者希望获得更大收益，想要将整个雪场打造成新手雪场。改造某座雪山海拔高度的成本为：变更高度的平方。注意： 变更高度仅可为整数； 变更工程可增加雪山海拔，也可降低雪山海拔； 请问雪场经营者改造需要投入的最少成本是多少（即：所有改造雪山的成本之和）？ 答案需要取模 1e9+7 （ 1000000007 ），如计算初始结果为：1000000008，请返回 1 。 示例 1： 输入：altitude = [5,1,4,3,8], difference = 3 输出：8 解释：将 1 变成 3，8 变成 6，这时最高是 6，最小是 3，相差不超过 3 。需要成本为：2^2 + 2^2 = 8 示例 2： 输入：altitude = [1,2,99999,3,100000], difference = 3 输出：998679962 解释：将 1，2 和 3 分别变为 40000，将 99999 和 100000 分别变为 40003，此时最高为 40003，最低为 40000，相差不超过 3，此时需要成本为 11998680039，为最小值，取模后为 998679962 提示： 1 <= altitude.length <= 10^5 1 <= altitude[i],difference <= 10^5
想了好久没思路，没找到原题
1 条回复 • 2020-04-26 18:01:43 +08:00
 |
1
misdake 2020-04-26 18:01:43 +08:00
“低于范围的山的成本”和“高于范围的山的成本”，这两个的差的绝对值最小的时候是不是和也最小？(因为成本是高度差的平方，类似于最小二乘法，不过“范围内成本为 0”这一点可能会影响结论)
如果是的话，可以二分求答案，去找上下两个成本的差最小的结果，然后+1 、-1 也试一下，3 个结果里取成本最小值。 |
Select Language