プログラムの実行時間をできるだけ短くしたいです。
最終的なゴールは、入力Nを読み込み、評価して2つの連結リストにそれぞれ結果をストアし、その結果を順に出力することです
入力の条件は、
The first line contains the integer N. The second line contains N integers, a0,a1,...,aN−1. The integers are separated by a single space character. The third line contains N integers, b0,b1,...,bN−1. The integers are separated by a single space character.
となっています。
タイムリミットは1s,入力数は<1000000です。
現時点では、
scanf("%d", &N) //入力される要素数
for(i=0;i<N;i++)
scanf("%d",&a[i]);
for(i=0;i<N;i++){
scanf("%d",&b[i]); //aiの範囲を指定する数bi
for(i=0;i<N;i++){
for(j=1;j<b[i];j++){
if(i+j)<N){
if(a[i+j]<a[i]){
R[i] = (i+j) //配列に代入
}
}
}
}
for(i=0;i<N;i++){
for(j=1;j<b[i];j++){
if((i-j)>=0){
if((a[i-j]<a[i])){
L[i] = (i-j) //配列に代入
}
}
}
}
for(i=0;i<N;i++)
printf("%d %d\n",L[i],R[i])//L,Rの要素をすべて出力
というようなコードを書きました。これだとTLEを返されてしまいますが、これ以外の方法が思いつかなくて詰まっている状態です。スタックを使う方法も考えてみましたが具現化できませんでした。どうかお力添えいただけると幸いです。
(今朝同じような質問をさせていただきましたが当初と質問が変わったため質問し直させていただきました。不慣れですみません。)
追記1
if(a[i+j]<a[i]){
R[i] = (i+j) //配列に代入
}
この部分では、biの範囲中にある最も遠い(インデックスの値が大きい)ajを取得したいのでaを複数回代入することになっています
追記2
コメントで指摘いただいた点を直してみましたがやはりTLEになってしまいました…データ構造に関する問題なので上手にそれらを活用できないかな?と思っています。
if((i+j)<N){...}
となっている部分は else clause が無いので、for(j=1;(j<b[i])&&((i+j)<N);j++){if(a[i+j]<a[i]){...}}
と書き変える事ができます。配列b
の要素の値にもよりますが、最悪でもループの実行回数はN*(N-1)
になります。次にif(a[i+j]<a[i]){R[i]=(i+j)}
の部分ですが、配列a
の要素の値によっては代入(R[i]=(i+j)
)が複数回行われる事もあり得ます。問題文の肝心の部分が記載されていないので不明なのですが、一度でもa[i+j]<a[i]
が成立すれば(代入操作を行って)ループ処理を打ち切る(break loop)、という条件になっているのではないでしょうか?for(j=initial_value;end_condition;j--){...}