Минимальная сумма всего времени в пути

Я нашел в Интернете загадку на intervalStreet и попытался решить ее следующим образом:

Существует бесконечная целочисленная сетка, в которой N людей имеют свои дома на. Они решают объединяйтесь в общем месте встречи, которым является чей-то дом. Из любой ячейки все 8 соседние ячейки достижимы за 1 единицу времени. например: (x, y) можно получить из (x-1, y + 1) за единицу времени. Найдите общее место встречи, которое минимизирует сумму время в пути всех людей.

Сначала я подумал о написании решения в n² сложности по времени, но ограничения

1

Итак, я изменил свой первый подход и вместо того, чтобы рассматривать проблему с расстояниями и временем в пути, я смотрел на разные дома как на разные тела с разным весом. И вместо того, чтобы вычислять все расстояния, я ищу центр тяжести группы тел.

Вот код моей функции "решения", vectorToTreat - это таблица lengthX2, в которой хранятся все данные о точках на сетке и resul - это число, которое нужно вывести на стандартный вывод:

long long solve(long long** vectorToTreat, int length){
    long long resul = 0;
    int i;
    long long x=0;
    long long y=0;
    int tmpCur=-1;
    long long tmp=-1;
    for(i=0;i

Проблема в том, что я прошел 12 официальных тестовых случаев за 13 и не вижу, что я делаю неправильно, есть идеи? Заранее спасибо. AE

16
задан templatetypedef 24 August 2011 в 17:17
поделиться