Быстрый алгоритм поиска симметричной точки
От: RomanRoschin  
Дата: 08.09.05 12:23
Оценка:
Вот возникла такая задачка. Пусть дан массив целых числе размера N: c[0], c[1], ... c[N-1]
Будем считать что число i правее числа j если 0 < (i-j) mod N < N/2. Всего таких чисел целая часть от (N-1)/2.
Обозначим VR(j) = sum_{i правее j} c[i], VL(j) = sum_{i левее j} c[i], V(j) = abs(VR(j)-VL(j)).
Найти такое j при котором V(j) минимально.

Очевидный алгоритм решения (перебор) требует время порядка O(N^2). Можете ли быстрее?
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.