USACO Ski Course Design解題レポート

ここではnaiveの手法を用いて、すべての高さの組み合わせ(改造後の)(最低高さ、最高高さ)をテストする.最低高さの範囲は[low,high-17]からである.lowとhighはそれぞれ現在の最低高さと最高高さである.高さの種類は少ない(0~100)ため、ここでは1つの配列(cnt)で各カテゴリの高さを統計する.

/* 
ID: thestor1 
LANG: C++ 
TASK: skidesign 
*/
#include <iostream>
#include <fstream>  
#include <cmath>  
#include <cstdio>  
#include <cstring>  
#include <climits>  
#include <cassert>  
#include <string>  
#include <vector>  
#include <set>
#include <map>  
#include <queue>  
#include <stack>  
#include <algorithm>
#include <cassert>

using namespace std;

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

	int N;
	fin>>N;
	std::vector<int> cnt(101, 0);
	for (int i = 0; i < N; ++i)
	{
		int height;
		fin>>height;
		assert(0 <= height && height <= 100);
		cnt[height]++;
	}

	int low = 0, high = 100;
	
	while (cnt[low] == 0)
	{
		low++;
	}
	
	while (cnt[high] == 0)
	{
		high--;
	}

	int mincost = -1;
	for (int l = low; l <= high - 17; ++l)
	{
		int h = l + 17;
		int cost = 0;
		for (int i = low; i < l; ++i)
		{
			if (cnt[i])
			{
				cost += (l - i) * (l - i) * cnt[i];
			}
		}
		for (int i = high; i > h; --i)
		{
			if (cnt[i])
			{
				cost += (i - h) * (i - h) * cnt[i];	
			}
		}
		if (mincost < 0 || cost < mincost)
		{
			mincost = cost;
		}
	}

	fout<<max(mincost, 0)<<endl;

	fin.close();
	fout.close();
	return 0;  
}