Вам были предоставлены следующие массивы:
x[n] - x[i] denotes the x coordinates of ith city
y[n] - y[i] denotes the y coordinate of the ith city
p[n] - p[i] denotes the population of the ith city
Учитывая координаты и численность населения каждого города в двухмерной плоскости, цель состоит в том, чтобы найти идеальную точку встречи для всех n городов.так что стоимость проезда всех городов до точки составляет минимум .
Let that meeting point be (x,y)
Travel cost for city i having coordinates (x[i], y[i]) and population of p[i] is:
p[i] * (abs(x[i] - x) + abs(y[i] - y)), abs() is the absolute value, and (abs(x[i] - x) + abs(y[i] - y)) is the distance to reach (x,y) from (x[i], y[i])
Я точно не помню ограничений, но, думаю, это было 1 <= n <= 100,000
Мой подход Первоначально я думал, что эта проблема аналогична нахождению центра тяжести дискретных распределений масс, где масса была аналогична населению, а центральной точкой встречи был CG.И поскольку это был «Центр», общая стоимость поездки должна быть минимальной.
for(i = 0; i < n; i++)
{
x += x[i]*p[i];
y += y[i]*p[i];
sum += p[i];
}
x /= sum;
y /= sum;
Затем вычислим стоимость:
for(i = 0; i < n; i++)
{
cost += p[i]*(abs(x[i] - x) + abs(y[i] - y));
}
Но потом я обнаружил, что, хотя он прошел тестовые примеры, он не прошел все остальное.И я выяснил, если бы это были соответствующие значения массивов
x[] = {3,1}
y[] = {3,1}
p[] = {2,1}
Тогда CG был бы (2,2) со стоимостью 6, но если бы вместо этого место встречи было в (3,3),стоимость могла быть 4, что минимально.Итак, есть ли что-то в качестве центра этого распределения, и если / если нет, то как найти место встречи, учитывая данное ограничение?