Я нашел в Интернете загадку на 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