Мобильная версияПеред вами в очереди N человек, 1, 2, …, N. Вы знаете,
что человек на i-й позиции займет Ai единиц времени. Вы можете
подкупить человека перед вами на сумму Bi (это
его положение) и обменяться с ним позициями. Вы можете подкупить
несколько человек, но подкупить только того, кто перед вами. Поскольку
время — деньги, каждая единица времени в точности равна единице денег.
Предполагая, что подкуп человека и обмен с ним позициями происходит
мгновенно, вам нужно указать наименьшую сумму денег, которую вам нужно
потратить, чтобы оказаться впереди очереди.
Далее в очереди будут Q обновлений, и вам нужно будет сообщить ответ
для исходного дела и каждого дела после его создания. обновление.
Кроме того, обновления являются постоянными. Пример:
A: 1 5 3 2, B: 7 2 1 9
Обновление 1, i = 1, a = 3, b = 1
A: 3 5 3 2, B: 1 2 1 9
Обновление 2: i = 3, a = 4, b = 8
A: 3 5 4 2, B : 1 2 8 9
Рассчитайте минимальные деньги, которые вам придется потратить, чтобы занять 1-е место для исходного сценария и для каждого сценария после обновления Q.
Входные данные: 1-я строка: N
2-я строка: N целых чисел, A1, A2, …, An.
3-я строка: N целых чисел, B1, B2, …, Bn.
4-я строка: Q
Следующие Q строк, где каждая строка представляет собой:
i, a и b
в каждом обновлении A = a и B = b.
Мой подход к решению этого вопроса заключался в вычислении префиксных сумм массива A
с начала и массива B с конца.
и затем для каждой позиции i я рассчитываю стоимость того, чтобы оказаться перед очередью, стоя там после подкупа всех до этой позиции. И берем минимум из всех.
Итак, для позиции i это будет A[i-1] + B.
Затем, после каждого обновления, я пересчитываю сумму префиксов для A и B из индекса i и снова нахожу минимум i.
И в худшем случае сложность будет: O(N * Q).
Это решение работало для запуска подзадач, но ограничение по времени было превосходит некоторые задачи последующих подзадач.
Есть ли способ дальнейшей оптимизации этого подхода или может ли существовать совершенно новый, лучший подход к этой проблеме?
Насколько я помню, это был мой код:
Код: Выделить всё
#include
using namespace std;
int main()
{
int N, Q, *A, *_A, *B, *_B;
cin >> N;
//Easier to calculate prefix sums
//A1 is stored at index 1, B2 is stored at index 1
//So A[1] + B[1] is A1 + B2
//So is A[0] + B[0] is 0 + B1 (Bribe everyone case)
//And so is A[N] + B[N] is AN + 0 (Bribe no one case)
A = new int[N + 1];
B = new int[N + 1];
_A = new int[N + 1];
_B = new int[N + 10];
A[0] = 0;
_A[0] = 0;
B[N] = 0;
_B[N] = 0;
for (int i = 0; i < N; i++)
{
cin >> A[i + 1];
}
for (int i = 0; i < N; i++)
{
cin >> B[i];
}
cin >> Q;
int ai = 1;
int bi = N - 1;
int a, b;
int iterator = 0;
int _min;
while (iterator a >> b;
bi = ai-1;
A[ai] = a;
B[bi] = b;
}
iterator++;
}
return 0;
}
Код: Выделить всё
5
2 7 3 5 1
3 4 5 1 1
2
2 1 7
3 13 2
Код: Выделить всё
13 8 7
Изначально массив A равен 2 7 3 5 1, а B равен 3 4 5 1 1
Минимальные деньги, которые мы должны потратить, составляют 13, находясь на позиции 2 после подкупа людей до этой позиции за (1+1+2+7) = 11 и ожидая, пока человек (люди) перед нами перейдут (2), Итого sum = 2 + 11 = 13.
Далее мы получаем обновление i = 2, a = 1 и b = 7.
Массив A теперь равен 2 1 3 5 1, а B равен 3 7 5 1 1.
Минимальная сумма денег, которую мы должны потратить, равна 8, находясь на позиции 4 после подкупа людей до этой позиции для (1+1) = 2 и ждём, пока человек(а) перед нами двинется (2+1+3) = 6, Общая сумма = 2 + 6 = 8.
Далее мы получаем обновление i = 3, a = 13 и b = 2.
Массив A теперь равен 2 1 13 5 1, а B равен 3 7 2 1 1.
Минимум деньги, которые мы должны потратить, равны 8, находясь в позиции 3 после подкупа людей до этой позиции для (1+1+2) = 4 и ожидания, пока человек(и) перед нами перейдут (2+1) = 3, общая сумма = 4 + 3 = 7.
И ответ для первого случая, 2-го случая и 3-го случая - 13, 8 и 7 соответственно. Итак, мы выводим 13 8 7
Подробнее здесь: https://stackoverflow.com/questions/798 ... m-question
