Cod sursa(job #1047338)

Utilizator hotfixVasile Pantelescu hotfix Data 4 decembrie 2013 11:34:48
Problema Tribute Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;

int compute_the_best_distance(int* hist, int MAX_VAL, int N, int d)
{
	//find the median
	int median = -1,  howMany = 0;	
	while (howMany < (N+1) / 2) howMany += hist[++median];

	int* CH = new int[MAX_VAL + 1]; //the cummulative histogram
	CH[0] = hist[0];
	for (int k = 1; k <= MAX_VAL; k++) CH[k] = hist[k] + CH[k - 1];

	//compute the total distance F[k] to the interval [median - d + k, median + k]
	int* F = new int[d+1];	

	//compute F[0]:	
	F[0] = 0;
	for (int i = 0; i < median - d; i++) F[0] += hist[i] * (median - d - i);
	for (int i = median + 1; i <= MAX_VAL; i++) F[0] += hist[i] * (i - median);

	//recursivelly compute F[1], F[2], ...
	for (int k = 1; k <= d; k++)
	{
		int ch1 = 0;
		if (median - d + k - 1 >= 0) ch1 = CH[median - d + k - 1];
		int ch2 = CH[MAX_VAL];
		if (median + k - 1 < MAX_VAL) ch2 = CH[median + k - 1];
		F[k] = F[k - 1] + ch1 - (CH[MAX_VAL] - ch2);
	}

	//obtain the minimum distance
	int min_distance = F[0];
	for (int k = 1; k <= d; k++) if (F[k] < min_distance) min_distance = F[k];

	//release the memory
	delete[] F;
	delete[] CH;

	return min_distance;
}

//int pb_028_tribute()
int main()
{
	string in_file = "tribute.in";
	string out_file = "tribute.out";

	const int MAX_N = 50001;
	const int MAX_VAL = 50001;

	int N, dx, dy;

	int histx[MAX_VAL + 1], histy[MAX_VAL + 1];
	for (int k = 0; k <= MAX_VAL; k++) histx[k] = histy[k] = 0;

	//read the inputs
	ifstream ifs(in_file);
	ifs >> N >> dx >> dy;
	//read all the coordinates of the objects
	//stores the coordiantes in a histogram
	for (int k = 0; k < N; k++)
	{
		int x, y;
		ifs >> x >> y;
		histx[x]++; histy[y]++;
	}
	ifs.close();
	
	int total_distance_x = compute_the_best_distance(histx, MAX_VAL, N, dx);
	int total_distance_y = compute_the_best_distance(histy, MAX_VAL, N, dy);

	ofstream ofs(out_file);
	ofs << total_distance_x + total_distance_y;
	ofs.close();

	return 0;
}