Как мне дополнительно оптимизировать этот вопрос о сумме префиксов? ⇐ C++

[Anonymous]

У меня была такая проблема на соревновании по программированию:

Перед вами в очереди 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 
#undef HUGE
#define HUGE 0x70000000

using namespace std;

int main()
{
int TPeople, TUpdates, *ExitTime, *BribeSum;

cin >> TPeople >> TUpdates;

ExitTime = new int[TPeople+1];
BribeSum = new int[TPeople+1];
ExitTime[0] = 0;
BribeSum[TPeople] = 0;

//ExitTime1 is stored at ExitTime[1]
for(int i = 1; i > ExitTime[i];
}

//BribeSum1 is stored at BribeSum[0]
for(int i = 0; i < TPeople; i++)
{
cin >> BribeSum[i];
}

//Calculate Prefix
for(int i = 1; i = 0; i--)
{
BribeSum[i] = BribeSum[i+1] + BribeSum[i];
}

int _min = HUGE;

//For each position i, the cost to be there is i-1th ExitTime + ith BribeSum
//As BribeSum for ith person is stored at BribeSum[i-1], BribeSum[i] refers
//to the bribe for the i+1th person
//So ExitTime[i] + BribeSum[i] is actually: ith ExitTime + i+1th BribeSum
//When below i = 0; ExitTime[i] + BribeSum[i] is ExitTime[0](0 as set before) + i+1th BribeSum (Case when everyone is bribed)
//When below i = TPeople; ExitTime[i] + BribeSum[i] is nth ExitTime + BribeSum[TPeople](0 as set before) (Case when no one is bribed)
for(int i = 0; i > newExitTime >> newBribeCost;

// Calculates the actual/original value of ith ExitTime
original = ExitTime[i] - ExitTime[i-1];
exitTimeDiff = newExitTime - original;

// Calculates the actual/original value of ith BribeSum
// ith BribeSum is stored at BribeSum[i-1]
//  BribeSum[i-1] - BribeSum[i] is ith BribeSum - i+1th BribeSum
original = BribeSum[i-1] - BribeSum[i];
bribeCostDiff = newBribeCost - original;

// Add the difference to ExitTime prefix and BribeSum suffix
for(int ai = i; ai = 0; bi--)
{
BribeSum[bi] += bribeCostDiff;
}

// Calculate the minimum again.
for(i = 0; i 

Подробнее здесь: [url]https://stackoverflow.com/questions/79885597/how-do-i-further-optimize-this-prefix-sum-question[/url]