srm_346_div_1_500.cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <limits.h>

#include <string>
#include <sstream>

using namespace std;

int getMinDiff(vector<int> heights) {
	int min_diff = INT_MAX;
	for (int i = 0; i < heights.size(); i++) {
		int a = heights[i];
		int b = (i == heights.size() - 1) ? heights[0] : heights[i + 1];
		
		int diff = abs(a - b);
		if (diff < min_diff) {
			min_diff = diff;
		}
	}
	
	return min_diff;
}

int getMaxDiff(vector<int> heights) {
	int max_diff = 0;
	for (int i = 0; i < heights.size(); i++) {
		int a = heights[i];
		int b = (i == heights.size() - 1) ? heights[0] : heights[i + 1];
		
		int diff = abs(a - b);
		if (diff > max_diff) {
			max_diff = diff;
		}
	}
	
	return max_diff;
}

bool compare_int(const int a, const int b)
{
	std::ostringstream a_s;
	std::ostringstream b_s;
	a_s << a;
	b_s << b;

	return a_s.str() < b_s.str();
}

vector<int> getBestRound(vector<int> heights) {
	// The base idea is insertion sort
	
	// Sort
	sort(heights.begin(), heights.end(), greater<int>());
	
	// Create a new vector having results
	vector<int> result;
	for (int i = 0; i < heights.size(); i++) {
		int height = heights.at(i);
		
		if (result.size() < 3) {
			result.push_back(height);
			continue;
		}
		
		// Find the best position to insert
		int best_index = 0;
		int min_diff_left = abs(result.at(result.size() - 1) - height);
		int min_diff_right = abs(result.at(0) - height);
		//int best_index = result.size();
		//int min_diff_left = abs(result.at(best_index - 1) - height);
		//int min_diff_right = abs(result.at(0) - height);
		
		for (int j = 1; j < result.size(); j++) {
		//for (int j = result.size() - 1; j > 0; j--) {
			int diff_left = abs(result.at(j - 1) - height);
			int diff_right = abs(result.at(j) - height);
			
			if ((diff_left < min_diff_left && diff_right < min_diff_right) ||
			    ((diff_left + diff_right) < (min_diff_left + min_diff_right))) {
			//if ((diff_left + diff_right) < (min_diff_left + min_diff_right)) {
				best_index = j;
				min_diff_left = diff_left;
				min_diff_right = diff_right;
			}
		}
		
		// Insert
		result.insert(result.begin() + best_index, height);
	}
	
	return result;
}

void test(const char * name, vector<int> heights) {
	vector<int> result = getBestRound(heights);
	
	cout << name << ":";
	for (int i = 0; i < result.size(); i++)
		cout << " " << result.at(i);
		
	int min_diff = getMinDiff(result);	
	int max_diff = getMaxDiff(result);		
	cout << " (" << min_diff << ", " << max_diff << ")";

	cout << endl;
}

int main(int argc, char *argv[]) {
	int test1_a[] = {1, 2, 4, 3};
	vector<int> test1;
	test1.push_back(1);
	test1.push_back(2);
	test1.push_back(4);
	test1.push_back(3);
	
	vector<int> test2;
	test2.push_back(1000);
	test2.push_back(500);
	test2.push_back(1);
	
	vector<int> test3;
	test3.push_back(1);
	test3.push_back(3);
	test3.push_back(4);
	test3.push_back(5);
	test3.push_back(7);
	
	vector<int> test4;
	test4.push_back(1);
	test4.push_back(1);
	test4.push_back(1);
	test4.push_back(1);

    int test5_a[] = {1,3,6,11,15,21,27,34,42,50,59,68,78,89,100,111,124,136,149,163,177,191,207,222,238,254,271,289,306,324,343,362,381,401,422,442,463,485,507,529,552,575,598,622,646,671,696,721,747,773};
	vector<int> test5;
	test5.assign(test5_a, test5_a + sizeof(test5_a) / sizeof(test5_a[0]));
	
	vector<int> test6;
	test6.push_back(1);
	test6.push_back(1);
	test6.push_back(1);
	test6.push_back(2);
	test6.push_back(2);
	test6.push_back(3);
	
	vector<int> test7;
	test7.push_back(1);
	test7.push_back(1);
	test7.push_back(8);
	test7.push_back(10);
	
	vector<int> test8;
	test8.push_back(1);
	test8.push_back(90);
	test8.push_back(100);
	test8.push_back(110);
	test8.push_back(1000);
	test8.push_back(101);
	test8.push_back(91);
	
	cout << "" << endl;
	test("test1", test1);
	test("test2", test2);
	test("test3", test3);
	test("test4", test4);
	test("test5", test5);
	test("test6", test6);
	test("test7", test7);
	test("test8", test8);
}