Problem 1.4.8 Ski Course Design

출처: https://train.usaco.org/usacogate

---

문제 설명

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.

입력 

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

출력

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.

입력 예

5 
20 
4 
1 
24 
21 

출력 예

18 

---

문제 풀이 내용

가능한 높이차들 (100, 83) ~ (17,0) 안으로 모든 산들을 갈아 넣는다. 이렇게 만든 작업량중에 가장 제일 적은 것을 찾는다.

프로그램 내용

...
/// sort hill height
sort(hills.begin(), hills.end(),compare1);

int mincost=10000000; /// max work: 1000*100

for(int idx=0; idx < 83 ; ++idx)
	int cost, work; 
	for (int idx2 = 0; idx2 < num_hills ; ++idx2) /// (0, 17) ~ (83,100)
		if (hills[idx2]<idx) // if hill is below the interval
        	work = idx - hills[idx2];
		else if (hills[idx2]> idx+17) // if hill is above the interval
        	work = hills[idx2]-(idx+17);
		else
			work = 0;
		cost+= work*work;
		mincost=min(mincost,cost);
 ...

 

Chapter 1. Getting started