Pagini recente » Cod sursa (job #98907) | Cod sursa (job #1667080) | Cod sursa (job #2732916) | Cod sursa (job #165229) | Cod sursa (job #1047338)
#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;
}