Pagini recente » Cod sursa (job #3130987) | Cod sursa (job #1729898) | Cod sursa (job #2822197) | Cod sursa (job #1118465) | Cod sursa (job #1047299)
#include <iostream>
#include <fstream>
#include <string>
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++) F[k] = F[k - 1] + CH[median - d + k - 1] - (CH[MAX_VAL] - CH[median + k-1]);
//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 = 50000;
const int MAX_VAL = 50000;
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;
}