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番目のタスクは最初の反復中に完了し、2秒で終了します。3番目の反復では、3番目と4番目のタスクはそれぞれ11秒と12秒で完了します。最後に、8回目の反復で、最初と最後のタスクはそれぞれ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

まず、SPOJまたは任意のg++コンパイラのC/C++でのintの制限は2^31であり、これは10 ^ 9を少し超えるため、10^9を50,000倍追加すると約5*10^13になることを理解する必要があります。 、合計変数は保持できません。

上記の問題が修正されたとしても、プログラムは実行可能な時間内に実行されません。最新のプロセッサでさえ、1秒あたり10^9命令の一定時間までしか処理できません。ただし、プログラムの実行が完了するまでには、それよりも多くの時間が必要になる場合があります。（どれくらいの時間がかかるかは正確には言えませんが、おおよその目安として、最悪の場合は約13時間で5万秒以上かかることは間違いありません）

SPOJの問題の解決策を提出するときはいつでも、これらの制約を念頭に置いておく必要があります。

于 2012-03-09T05:51:07.020 に答える
2

まず第一に、Chakradar Rajuが言ったように、手順全体をエミュレートすることは、その広大な範囲の仕事を実装するための良い方法ではありません。また、intよりも範囲が広い型を使用する必要があります。たとえば、64ビットintであるlonglongのようなものです。

そして、それを解決するための良いアルゴリズムを見つけてみてください。私は方法を提供し、それがうまくいくことを望みます。

毎回、iという番号のタスクを検討し、i番目のタスクの最後の1秒になると、すべてのタスクが終了よりも短くなります。私たちは彼らの費用を合計する必要があるだけです。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つだけなので、3回目だけ実行されます。それと3回目の処理自体を追加します。結果は1+8 + 1 + 1=11秒です。

コーディングするときは、タスクのシーケンス番号を覚えて、処理時間で並べ替える必要があります。次に、すべてのタスクが短くなり、その前になります。左側のジョブは線形時間処理であり、ソートにはO（nlogn）時間計算量が必要です。これは、ジョブを完了するのに十分な速度です。

于 2012-03-09T06:41:23.890 に答える