USACO 1.3 Ski Course Design

At first glance, a reasonable approach seems to sort the heights of hills then starting from both ends (smallest and biggest), adjust and iterate and converge to a fixed point. However, the problem has a constraint that for each hill only a single change can be made, so this would not work. Think in the other direction, given the constraints each hill has to end up with a height that’s fall in the range of 0 to 83 (inclusive), so we can simply use brutal force to iterate that for each range, what would be the overall cost to adjust all hills.

#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <cmath>
#include <climits>

using namespace std;

int N;
vector<int> hills;
int compute() {
  int ret = INT_MAX;
  for (int i = 0; i < 83; ++i) {
    int result = 0;
    for (auto &h : hills) {
      if (h < i) {
        result += pow(i - h, 2);
      }
      if (h > i + 17) {
        result += pow(h -i - 17, 2);
      }
    }
    ret = min(ret, result);
  }
  return ret;
};

int main() {
  ifstream fin("skidesign.in");
  ofstream fout("skidesign.out");

  fin >> N;
  for (int i = 1; i <= N; ++i) {
    int h;
    fin >> h;
    hills.emplace_back(h);
  }

  int ret = compute();
  cout << ret << endl;
  fout << ret << endl;
}