Вот строгое доказательство, если кому интересно. Давайте для начала положим всех программистов в первую команду, при этом их эффективность будет равна сумме всех a_i, обозначим ее за S. Теперь нужно переместить (n / 2) программистов во вторую команду. При перемещении программиста из первой команды во вторую суммарная эффективность изменяется на -a_i + b_i. Нужно выбрать ровно n / 2 человек, и для всех них прибавить к S (-a_i + b_i). Логично, что среди всех n чисел (-a_i + b_i) нужно выбрать (n / 2) максимальных, чтобы итоговая сумма была максимальна. А для обработки запросов на изменение, нужно поддерживать сумму a_i, и сумму (n / 2) максимальных (-a_i + b_i). Второе поддерживается с помощью std::multiset, например.
Давайте рассмотрим множество M_2, будем считать его gcd по-очереди добавляя в gcd числа из M_2. Пусть g — текущее значение gcd, и мы берем gcd(g, a_i). Где a_i — очередной элемент M_2. Будем рассматривать рекурсивную реализацию gcd.
int gcd(int a, int b) {
return b == 0? a: gcd(b, a % b);
}
Тогда на глубине рекурсии, равной 2, значения a и b не превосходят значения g. А так, как при каждом новом уходе в рекурсию итоговое значение gcd уменьшается в 2 раза, после вычисления gcd, g уменьшится в 2^(h — 1) раз, где h — глубина рекурсии. Так как, g мы поддерживаем по ходу, оно может уменьшится в 2 раза не более логарифма раз. В итоге, вычисление gcd множества M_2 будет работать за O(|M_2| + log(max(a_i)))
Вроде, как-то так :)
Information
Rating
Does not participate
Location
Санкт-Петербург, Санкт-Петербург и область, Россия
int gcd(int a, int b) {
return b == 0? a: gcd(b, a % b);
}
Тогда на глубине рекурсии, равной 2, значения a и b не превосходят значения g. А так, как при каждом новом уходе в рекурсию итоговое значение gcd уменьшается в 2 раза, после вычисления gcd, g уменьшится в 2^(h — 1) раз, где h — глубина рекурсии. Так как, g мы поддерживаем по ходу, оно может уменьшится в 2 раза не более логарифма раз. В итоге, вычисление gcd множества M_2 будет работать за O(|M_2| + log(max(a_i)))
Вроде, как-то так :)