Минимальные изменения, необходимые в массиве, чтобы сумма смежных элементов была одинаковой
Этот вопрос задают во время онлайн-собеседования:
Существует служба с n серверами, и i-й сервер имеет вычислительную мощность в единицах server[i].
Пользователь может назначить k различных задач любому непрерывному сегменту серверов от индекса i до (i+k-1) для любого допустимого индекса i.
Чтобы обеспечить согласованное поведение, мы хотим, чтобы суммы вычислительных мощностей любого из этих подмассивов были равны.
Для этого мы можем заменить любой сервер новым сервером любой вычислительной мощности.
Учитывая сервер массива и целое число k, найдите минимальное количество серверов, которые необходимо заменить, чтобы каждый смежный подмассив из k серверов имел равную сумму вычислительных мощностей.
- Пример Предположим, n = 4, сервер = [1, 2, 3, 2] и k = 2.
смежные суммы: [(1,2), (2,3), (3,2)] = [3,5,5] Оптимально заменить только первый сервер => [3,2,3,2] , непрерывная сумма теперь равна [(3,2), (2,3), (3,2)] = [5, 5,5] поэтому ответ 1.
2. Пример: предположим, n = 5, сервер = [1,2,1,1,2], k = 3.
смежная сумма = [(1,2,1), (2,1,1), (1,1,2)] = [4,4,4], поэтому ответ 0
Это код:
public static void main(String[] args) {
System.out.println(solve(2, Arrays.asList(1,2,3,2))); // correct is 1
System.out.println(solve(2, Arrays.asList(1,2,3))); // correct is 2
System.out.println(solve(3, Arrays.asList(1,2,1,1,2))); // correct is 0
}
private static int solve(int k, List<Integer> server) {
// here is my code, which fails for 2nd test case.
long sum = 0;
for(int i=0; i<k; i++) sum += server.get(i); // get sum of k items
long current = sum; // assign that to current
int result = 0;
int n = server.size();
for(int i=1; i<=n-k; i++) {
current += server.get(i+k-1) - server.get(i-1); // get group sum that starts with i
if (current != sum) result++; // found difference
if (current > sum) sum = current; // update sum if it is less than current
}
return result;
}
В своем коде я предположил, что для группы, начинающейся с i, замена будет выполняться только на сервере[i], но это предположение неверно для данной задачи. Каков правильный подход к решению этой проблемы.
Ответы 1
Сумма подмассива server[i+1...i+k] равна sum(server[i...i+k-1]) - server[i] + server[i + k] (удалить первый элемент и добавить следующий).
Поскольку все подмассивы размера k должны иметь одинаковую сумму, это напрямую означает, что server[i] = server[i + k]. Применяя ту же логику дальше, мы можем обнаружить, что server[i] должно равняться server[i + x*k] для всех целых чисел x (где i + x*k — допустимый индекс). Другими словами, все значения всех индексов, находящихся в одном классе эквивалентности по модулю k, должны быть равны.
Затем, чтобы решить эту проблему, мы можем просто заменить все элементы в одном классе эквивалентности наиболее распространенным элементом в этом классе эквивалентности (обратите внимание, что существует k различных классов эквивалентности по модулю k). Это O(N), поскольку каждый элемент обрабатывается ровно один раз.
static int solve(int k, List<Integer> server) {
int minChanges = 0;
for (int i = 0; i < k; i++) {
var count = new HashMap<Integer, Integer>();
int total = 0;
for (int j = i; j < server.size(); j += k, ++total)
count.merge(server.get(j), 1, Integer::sum);
minChanges += total - Collections.max(count.values());
}
return minChanges;
}
@Sid Когда мы переходим от одного подмассива к следующему, мы удаляем первый элемент и добавляем следующий элемент (как показано в первой части моего ответа). Итак, у нас есть sum(server[i...i+k-1]) + server[i+k] - server[i] = sum(server[i+1...i+k]). sum(server[i+1...i+k]) должна равняться sum(server[i...i+k-1]), поэтому server[i+k] - server[i] = 0 (путем вычитания sum(server[i...i+k-1]) из уравнения).
Спасибо, а в группе из k значений почему нам нужно иметь
server[i] = server[i + k]?