1353. 滑雪场设计
摘要
Title: 1353. 滑雪场设计
Tag: 模拟、贪心
Memory Limit: 64 MB
Time Limit: 1000 ms
Powered by:NEFU AB-IN
1353. 滑雪场设计
-
题意
农夫约翰的农场上有 N 个山峰，每座山的高度都是整数。
在冬天，约翰经常在这些山上举办滑雪训练营。
不幸的是，从明年开始，国家将实行一个关于滑雪场的新税法。
如果滑雪场的最高峰与最低峰的高度差大于17，国家就要收税。
为了避免纳税，约翰决定对这些山峰的高度进行修整。
已知，增加或减少一座山峰 x 单位的高度，需要花费 x2 的金钱。
约翰只愿意改变整数单位的高度，且每座山峰只能修改一次。
请问，约翰最少需要花费多少钱，才能够使得最高峰与最低峰的高度差不大于17。 -
思路
可以得知，高度在0到100，那么其实就可以枚举窗口的下限（因为要最高和最低的差在17以内，也就是所有山峰都在这个宽度为17的框里）即可，更新最小值
-
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25'''
Author: NEFU AB-IN
Date: 2022-05-15 21:52:35
FilePath: \ACM\Acwing\1353.py
LastEditTime: 2022-05-15 21:55:45
'''
n = int(input())
a = []
for i in range(n):
a.append(int(input()))
res = int(1e18)
for i in range(0, 84):
cost = 0
for j in range(n):
if a[j] < i:
cost += (i - a[j])**2
elif a[j] > i + 17:
cost += (a[j] - i - 17)**2
res = min(res, cost)
print(res)