18.12.21 luogu P3650 [USACO1.3]滑雪课程设计Ski Course Design

本文主要是介绍18.12.21 luogu P3650 [USACO1.3]滑雪课程设计Ski Course Design，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

农民约翰的农场里有N座山峰(1<=N<=1000),每座山都有一个在0到100之间的整数的海拔高度。在冬天,因为山上有丰富的积雪,约翰经常开办滑雪训练营。

不幸的是,约翰刚刚得知税法在滑雪训练营方面有新变化,明年开始实施。在仔细阅读法律后,他发现如果滑雪训练营的最高和最低的山峰海拔高度差大于17就要收税。因此,如果他改变山峰的高度（使最高与最低的山峰海拔高度差不超过17）,约翰可以避免支付税收。

如果改变一座山x单位的高度成本是x^2单位,约翰最少需要付多少钱?约翰只愿意改变整数单位的高度。

输入输出格式

输入格式：

第一行：一个整数n

第二行到N+1行：每行是一座山的海拔高度

输出格式：

约翰需要支付修改山海拔高度的总金额,最高和最低的山峰间高度差最多17。

输入输出样例

输入样例#1：复制

输出样例#1：复制

说明

约翰保持高度为4、20和21的山的高度。他增高高度为1的山、变成高度4(花费 3 ^ 2 = 9)。他降低了高度为24的山变成高度21也花费3 ^ 2 = 9。

 1 #include <iostream>
 2 #include <string.h>
 3 #include <algorithm>
 4 #include <stack>
 5 #include <string>
 6 #include <math.h>
 7 #include <queue>
 8 #include <stdio.h>
 9 #include <string.h>
10 #include <set>
11 #include <vector>
12 #include <fstream>
13 #define maxn 1005
14 #define inf 999999
15 #define cha 127
16 #define eps 1e-6 
17 #define oo 1503
18 using namespace std;
19 
20 int n, mountain[maxn];
21 
22 void init() {
23     scanf("%d", &n);
24     for (int i = 1; i <= n; i++)
25         scanf("%d", &mountain[i]);
26     int min0 = inf;
27     for (int i = 1; i <= 83; i++) {
28         int ans = 0;
29         for (int j = 1; j <= n; j++) {
30             if (mountain[j] > i + 17)
31                 ans += (mountain[j] - i - 17)*(mountain[j] - i - 17);
32             else if (mountain[j] < i)
33                 ans += (mountain[j] - i)*(mountain[j] - i);
34         }
35         min0 = min(ans, min0);
36     }
37     printf("%d\n", min0);
38 }
39 
40 int main() {
41     init();
42     return 0;
43 }