круговая реализация

Question

Компьютерному процессору дано N задач для выполнения (1 ≤ N ≤ 50000). Для i-й задачи требуется время обработки в секундах Ti (1 ≤ Ti ≤ 1 000 000 000). Процессор выполняет задачи следующим образом: каждая задача выполняется в порядке, от 1 до N, в течение 1 секунды, а затем процессор повторяет это снова, начиная с задачи 1. Как только задача завершена, она не будет запущена позднее итераций. Определите для каждой задачи общее время выполнения, прошедшее после ее завершения. Входные

Первая строка ввода содержит целое число N, а следующие N строк содержат целые числа от T1 до TN. Выход

Выведите N строк, i-я из которых содержит целое число, представляющее время, прошедшее с момента выполнения задачи i.

Пример

Введите: 5 8 1 3 3 8

Выход: 22 2 11 12 23

Второе задание завершается во время первой итерации, заканчиваясь через 2 секунды. На третьей итерации третье и четвертое задания завершаются за 11 секунд и 12 секунд соответственно. Наконец, на восьмой итерации первая и последняя задачи выполняются за 22 секунды и 23 секунды соответственно.

Что жуткий подход?

Это мой код:

#include <iostream>
using namespace std;
int main()
{
int n;
cin>>n;
int a[n];
int total=0;
for(int i=0;i<n;i++)
{cin>>a[i];total+=a[i];}
int b[n];
int j=0;
for(int i=0;i<total;i++)
{
        while(a[j%n]==0) j++;
        a[j%n]-=1;
        if(a[j%n]==0) b[j%n]=i+1; j++;
}
for(int i=0;i<n;i++)
cout<<b[i]<<endl;
system("pause");
return 0;
}    

но это не принимается на спой ...

Answer 1

Во-первых, как сказал Чакрадар Раджу, эмуляция всей процедуры не является хорошим способом реализовать работу для ее огромного диапазона.И вам нужно использовать типы с более широким диапазоном, чем int, например что-то вроде long long, которое является 64-битным int.

, а затем попытаться найти хороший алгоритм для его решения.Я предоставлю метод и хочу, чтобы он работал.

Каждый раз, когда мы рассматриваем задачу с номером i, а когда дело доходит до последней секунды i-й задачи, все задачи короче, чем она выполнена.Нам нужно только подвести итоги их стоимости.Для задач не короче i-й задачи, мы предполагаем, что i-я задача занимает Ti секунд.Задачи не короче этого и сама i-я задача работают как (Ti - 1) секунды, так и для своей (Ti) -ой обработки только задачи перед i-й задачей.Суммируйте их, и вы получите ответ.

Возьмите пример в качестве примера:

Для 1-го задания это занимает 8 секунд, а задачи короче, чем оно имеет 1 +3 + 3 = 7 секунд, затем для него и 5-го задания требуется 7 секунд, поэтому значение равно 7 * 2 = 14 секунд.Тогда нет задачи перед i-й задачей, поэтому нам нужно всего лишь добавить 1 секунду для самой 1-й задачи.Результат 7 + 14 + 1 = 22 * ​​1009 *

Может быть, это не совсем понятно, давайте посмотрим на 3-е задание, оно занимает 3 секунды, и только 1 задание короче его (второе, которое занимает 1 секунду).И все оставшиеся задачи занимают 3 - 1 = 2 секунды, это 4 * 2 = 8 секунд.Наконец, перед ним осталась только одна задача, так что только она запускается в третий раз.Добавляем и третий раз обрабатываем сам.Результат равен 1 + 8 + 1 + 1 = 11 секунд.

При кодировании необходимо запомнить порядковый номер задачи и отсортировать его по времени обработки.Тогда все задачи короткие, а затем их перед ним.Левое задание - это линейная обработка времени, и для сортировки требуется время (nlogn), которое достаточно быстро для завершения задания.

Answer 2

Во-первых, вы должны понимать, что предел int в C / C ++ в SPOJ или любом компиляторе g ++ составляет 2 ^ 31, что немного больше 10 ^ 9, поэтому при добавлении 50 000 раз 10 ^ 9 это будет около 5 *10 ^ 13, который не может содержать ваша общая переменная.

Даже если вышеупомянутая проблема устранена, ваша программа не запустится в любое возможное время.Даже самые последние процессоры могут обрабатывать до 10-9 команд в секунду.Но вашей программе может потребоваться больше времени, чем для завершения выполнения.(Я не могу точно сказать, сколько времени это займет, но, чтобы дать примерную идею, в худшем случае это наверняка займет более 50 000 секунд, что составляет почти 13 часов)

Всякий раз, когда вы отправляетеДля решения любой проблемы в SPOJ вы должны помнить об этих ограничениях.