USACO 1.3 - 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. 

출처: http://train.usaco.org/

N 개의 언덕으로 스키장을 만들려고 하는데 세금 문제를 피하기 위해서 가장 높은 언덕과 낮은 언덕의 차이가 17이 넘어가면 안됩니다. 따라서 언덕의 높이를 깍거나 높이려고 하는데 각 언덕은 한 번 씩만 깍거나 높일 수 있으며 각 언덕을 깍는데 깍은 높이^2 만큼의 비용이 들어갑니다. 이때 최소 비용을 구하는 문제입니다.

처음에는 완전 탐색으로 1씩 높이를 변경해가며 최소값을 구했지만 시간 복잡도가 너무 높아 옮겨야 될 높이를 먼저 구한 후 푸는 방법으로 풀었습니다.

my solving

c++

#include <fstream>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
 
const int maxDifference = 17;
int n;
vector<int> originalHills;
 
 
ll getCost(vector<int>& hills)
{
    ll ret = 0;
    for (int i = 0; i < n; i++)
    {
        ret += pow(originalHills[i] - hills[i], 2);
    }
    return ret;
}
 
ll changeHillHight()
{
    int lowest = originalHills[0];
    int highest = originalHills[n - 1];
    int heightTobeChanged = highest - lowest - maxDifference;
    
    ll ret = 999999999999999;
 
    for (int i = 0; i <= heightTobeChanged; i++)
    {
        vector<int> hills = originalHills;
        int changedHeight = lowest + i;
        for (vector<int>::iterator it = hills.begin(); it != hills.end(); it++)
        {
            if (*it < changedHeight)
                *it = changedHeight;
        }
        changedHeight = highest - heightTobeChanged + i;
        for (vector<int>::iterator it = hills.begin(); it != hills.end(); it++)
        {
            if (*it > changedHeight)
                *it = changedHeight;
        }
 
        ret = min(ret, getCost(hills));
    }
    return ret;
}
 
int main(void)
{
    ifstream fin("skidesign.in");
    ofstream fout("skidesign.out");
 
    fin >> n;
 
    for (int i = 0; i < n; i++)
    {
        int num;
        fin >> num;
        originalHills.push_back(num);
    }
    sort(originalHills.begin(), originalHills.end());
    
    fout << changeHillHight() << endl;
 
    fin.close();
    fout.close();
    return 0;
}