Ski Course Design

Farmer John has N hills on his farm (1 <= N <= 1,000), each with an integer elevation in the range 0 .. 100. In the winter, since there is abundant snow on these hills, FJ routinely operates a ski training camp.

Unfortunately, FJ has just found out about a new tax that will be assessed next year on farms used as ski training camps. Upon careful reading of the law, however, he discovers that the official definition of a ski camp requires the difference between the highest and lowest hill on his property to be strictly larger than 17. Therefore, if he shortens his tallest hills and adds mass to increase the height of his shorter hills, FJ can avoid paying the tax as long as the new difference between the highest and lowest hill is at most 17.

If it costs x^2 units of money to change the height of a hill by x units, what is the minimum amount of money FJ will need to pay? FJ can change the height of a hill only once, so the total cost for each hill is the square of the difference between its original and final height. FJ is only willing to change the height of each hill by an integer amount.

PROGRAM NAME: skidesign

INPUT FORMAT:

Line 1: The integer N.
Lines 2..1+N: Each line contains the elevation of a single hill.

SAMPLE INPUT (file skidesign.in):

5
20
4
1
24
21

INPUT DETAILS:

FJ's farm has 5 hills, with elevations 1, 4, 20, 21, and 24.

OUTPUT FORMAT:

The minimum amount FJ needs to pay to modify the elevations of his hills so the difference between largest and smallest is at most 17 units.

Line 1:

SAMPLE OUTPUT (file skidesign.out):

18

OUTPUT DETAILS:

FJ keeps the hills of heights 4, 20, and 21 as they are. He adds mass to the hill of height 1, bringing it to height 4 (cost = 3^2 = 9). He shortens the hill of height 24 to height 21, also at a cost of 3^2 = 9.


Submission file Name:  USACO Gateway |   Comment or Question

(转自[USACO]


  首先讲一下题目大意。有N座山峰,每座山峰的高度大于等于0小于等于100,由于下了雪,所以可以改造成滑雪场(倾盆大雪),但是如果最高的山峰和最低的山峰高度之差大于17政府就要收税,John为了不被收费,就决定改造山峰。把一座山峰的高度改动x,就会产生x2的费用。求最小的费用。

  鉴于数据范围较小,于是决定暴力,枚举改造后的最小高度,然后暴力每次跑一遍就可以了

Code

 /*
ID:
PROG: skidesign
LANG: C++11
*/
/**
* USACO
* Accepted
* Time:0ms
* Memory:4180k
*/
#include<iostream>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<fstream>
#include<sstream>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
typedef bool boolean;
#define INF 0xfffffff
#define smin(a, b) a = min(a, b)
#define smax(a, b) a = max(a, b)
template<typename T>
inline void readInteger(T& u){
char x;
int aFlag = ;
while(!isdigit((x = getchar())) && x != '-');
if(x == '-'){
x = getchar();
aFlag = -;
}
for(u = x - ''; isdigit((x = getchar())); u = (u << ) + (u << ) + x - '');
ungetc(x, stdin);
u *= aFlag;
} int n;
int *hills; inline void init(){
readInteger(n);
hills = new int[(const int)(n + )];
for(int i = ; i <= n; i++){
readInteger(hills[i]);
}
} int result = INF;
inline void solve(){
for(int res = ; res <= ; res++){
int cmp = ;
for(int i = ; i <= n; i++){
if(hills[i] < res){
cmp += (res - hills[i]) * (res - hills[i]);
}else if(hills[i] > res + ){
cmp += (hills[i] - res - ) * (hills[i] - res - );
}
}
smin(result, cmp);
}
printf("%d\n", result);
} int main(){
freopen("skidesign.in", "r", stdin);
freopen("skidesign.out", "w", stdout);
init();
solve();
return ;
}

最新文章

  1. Android使用最小宽度限定符时最小宽度的计算
  2. Ubuntu安装图形桌面
  3. Mybatis部分
  4. Mongodb2.6升级到Mongodb3.0.2笔记
  5. ArcGIS for Android学习(一)
  6. ASP.NET、WinForm - 判断整个页面文本框是否为空
  7. update与fixedupdate差别
  8. 『Tarjan算法 无向图的割点与割边』
  9. 2018-2019-2 《网络对抗技术》 EXP0 KALI安装 20165213 Week1
  10. python基础(十三) cmd命令调用
  11. Linux RPM、YUM、APT包管理工具
  12. Solve error LNK2001 about pcl::io::vtkPolyDataToPointCloud
  13. as3.0影片简介失效,不阻碍下面影片简介的事件
  14. c++四舍五入的新方法
  15. scikit-FEM-例1-求解Possion边值问题
  16. 【Oracle】强制关闭会话
  17. FSTConfiguration 高性能序列化框架FST
  18. [CSAcademy]Cycle Tree
  19. lambda(匿名函数)---基于python
  20. selenium的基本介绍

热门文章

  1. linux:用户及文件权限管理
  2. PAC 自动代理
  3. router-link params传参
  4. 【python-opencv】对象测量
  5. table切换(自己写)
  6. Mint linux中调整屏幕亮度的方法
  7. react.js 之 create-react-app 命令行工具系统讲解
  8. Py之np.concatenate函数【转载】
  9. [LeetCode] 476. Number Complement_Easy tag: Bit Manipulation
  10. STL学习笔记--特殊容器