c++ - 循环执行

Question

计算机处理器被赋予 N 个任务来执行(1 ≤ N ≤ 50,000)。第 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;
}    

但这在 spoj 上没有被接受......

Answer 1

首先，正如Chakradar Raju所说，模拟整个过程并不是一个很好的实现工作的方式，因为它的范围很大。并且您需要使用比 int 范围更广的类型，例如像 long long 这样的 64 位 int。

然后尝试找到一个好的算法来解决它。我将提供一种方法，并希望它有效。

每次，我们考虑一个编号为 i 的任务，当到第 i 个任务的最后一秒时，所有比它短的任务都完成了。我们只需要总结他们的成本。对于不短于第 i 个任务的任务，我们假设第 i 个任务花费 Ti 秒。不短于它的任务和第 i 个任务本身都工作 (Ti - 1) 秒，并且对于它们自己的 (Ti)th 个处理，只有第 i 个任务之前的任务工作。总结一下，你就会得到答案。

以样本为例:

对于第一个任务，它需要8秒，比它短的任务有1 + 3 + 3 = 7秒，那么它和第5个任务需要7秒，所以值为7 * 2 = 14秒。然后在第 i 个任务之前没有任务，所以我们只需要为第一个任务本身添加 1 秒。结果是 7 + 14 + 1 = 22

可能还不够清楚，我们来看第3个任务，耗时3秒，只有1个任务比它短(第二个耗时1秒)。剩下的所有任务需要 3 - 1 = 2 秒，即 4 * 2 = 8 秒。最后，它前面只剩下一个任务，所以只有它运行第 3 次。我们添加它和第三次处理本身。结果是 1 + 8 + 1 + 1 = 11 秒。

在编码时，您需要记住任务的序号并按处理时间对它们进行排序。然后所有的任务都比他们短。左边的作业是一个线性时间处理，排序的时间复杂度为O(nlogn)，可以很快完成作业。