1

一个计算机处理器有 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 接受...

4

2 回答 2

2

首先，正如 Chakradar Raju 所说，模仿整个过程并不是实施这项工作的好方法，因为它的范围很广。而且您需要使用范围比 int 更宽的类型，例如 long long 之类的 64 位 int。

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

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

以样本为例：

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

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

编码时，您需要记住任务的序列号并按处理时间对其进行排序。然后所有的任务都很短，然后它们就在它之前。左边的作业是线性时间处理，排序需要 O(nlogn) 时间复杂度，足够快完成作业。

于 2012-03-09T06:41:23.890 回答
2

首先，您应该了解 SPOJ 或任何 g++ 编译器中 C/C++ 中的 int 限制为 2^31，略大于 10^9，因此将 50,000 乘以 10^9 将使其约为 5*10^13 ，你的总变量不能保持。

即使上述问题得到纠正，您的程序也不会在任何可行的时间内运行。即使是最新的处理器也只能每秒处理 10^9 条指令。但是您的程序可能需要更多时间才能完成执行。（我不能确切地说需要多少时间，但给出一个大概的概念，在最坏的情况下肯定需要超过 50,000 秒，也就是将近 13 个小时）

每当您为 SPOJ 中的任何问题提交解决方案时，您都必须牢记这些限制。

于 2012-03-09T05:51:07.020 回答