次のハッカーブランクプログラムを最適化する

Question

ハッカーランクの問題ですべてのテストケースを通過するように、私が作成した次のコードを最適化したいと思います。現時点では動作しますが、タイムアウトのためにいくつかのケースで失敗します。あなたはコンセプトを変更せずにコードを最適化する方法を教えてください。

QUESTION

アリスはアーケードゲームをプレイし、リーダーボードのトップに登るしたいと考えています。 彼女は各レベルを上回るので、彼女のランキングを追跡するのを手助けすることはできますか？このゲームはDense Rankingを使用しているため、リーダーボードは次のように動作します。

•スコアが最も高いプレーヤーがリーダーボードのランク番号です。

•等しいスコアを持つプレイヤーは同じランキング番号を受け取り、次のプレイヤーはすぐ次の順位番号を受け取ります。

たとえば、4人のプレイヤーは100,90,90、および80のスコアを持っています。これらのプレイヤーはそれぞれ1,2,2および3のランクを持ちます。

アリスが再生を開始すると、すでにn人がリーダーボードにいます。アリスはmレベルでプレイし、各レベルを通過した後の彼女の合計スコアを示します。各レベルを完了した後、アリスは彼女の現在のランクを知りたいと思っています。

あなたは、単調に減少するリーダーボードのスコアの配列と、ゲームの各レベルの別のアリスの累積スコアの配列が与えられます。整数を出力する必要があります。整数は、各レベルを渡した後、Aliceの現在のランクを示す必要があります。

入力フォーマット：

• 最初の行は、既にリーダーボード上のプレイヤーの数を表す、整数nが含まれています。
• 次の行には、それぞれのスコアの値を記述する、スペースで区切られた整数nが含まれています。
• 次の行には、アリスのビートのレベル数を示す整数mが含まれています。
• 最後の行には、各プレーヤーのそれぞれの値を記述する、スペースで区切られた整数mが含まれています。

出力フォーマット：

プリント整数。整数は、各レベルを通過した後のアリスのランクを示す必要があります。ここで

INPUT

7 
100 100 50 40 40 20 10 
4 
5 25 50 120 

OUTPUT

6 
4 
2 
1 

は私のコードです：

#include <math.h> 
#include <stdio.h> 
#include <string.h> 
#include <stdlib.h> 

struct player { 
    int rank; 
    int score; 
}; 

struct node { 
    struct player data; 
    struct node *next; 
}; 

int main() { 
    int n, i, m, temp, count = 1, x; 
    struct node *ptr, *head; 
    head = (struct node *)malloc(sizeof(struct node)); 
    ptr = head; 
    scanf("%d", &n); 
    for (i = 0; i < n; i++) { 
     scanf("%d", &x); 
     ptr->data.score = x; 
     if (x < temp) 
      count++; 
     ptr->data.rank = count; 
     temp = ptr->data.score; 
     ptr->next = (struct node *)malloc(sizeof(struct node)); 
     ptr = ptr->next; 
    } 
    ptr = NULL; 
    ptr = head; 
    scanf("%d", &m); 
    for (i = 0; i < m; i++) { 
     scanf(" %d", &x); 
     while (x < ptr->data.score) 
      ptr = ptr->next; 
     if (ptr->next == NULL) 
      ptr->data.rank = count + 1; 
     printf("%d\n", ptr->data.rank); 
     ptr = head; 
    } 
    return 0; 
} 

問題は私にありn私がAliceのランクを取っているたびに、リンクされたリストを始めから横断しているという事実。これを可能にする最適化は何でしょうか？

Answer 1

リーダーボードが単調増加するように、リーダーボードを表すリストを逆にします。リーダーボードがそのように注文されている場合は、最後の位置からリーダーボードをたどるだけで済みます。私。擬似コードとして

10/5 20/4 40/3 40/3  50/2  100/1  100/1   leaderboard 
5    25    50       120 score 
6    4    2       1  pos 

：あなたの例-入力用のリーダーボード（l[j]）でscore[i]の位置に基づいて、我々はscore[i + 1]がどこ、位置l[j + x]でなければならないことを知っているので

node n = leaderboard.reverse().head 

foreach score in scorelist: 
    while n != null and n.score > score 
     n = n.next 

    if n == null: 
     print 1 
    else: 
     print n.pos - 1 

これは動作します逆のリーダーボードのx > 0

Answer 2

temp変数を初期化しないため、コードに未定義の動作があります。最初の比較if (x < temp)には未定義の動作があるため、countは正しくインクリメントされません。

ポールのアプローチはO（N）にO（ N ^{2）から複雑さを低減するために非常に良い解決策です。}

#include <stdio.h> 
#include <stdlib.h> 

struct node { 
    int rank; 
    int score; 
    struct node *next; 
}; 

int main(void) { 
    int n, i, m, last = 0, rank = 1, x; 
    struct node *ptr, *head = NULL; 
    if (scanf("%d", &n) != 1) 
     return 1; 
    for (i = 0; i < n; i++) { 
     ptr = malloc(sizeof(*ptr)); 
     if (ptr == NULL) 
      return 1; 
     if (scanf("%d", &ptr->score) != 1) 
      return 1; 
     if (ptr->score < last) 
      rank++; 
     ptr->rank = rank; 
     last = ptr->score; 
     ptr->next = head; 
     head = ptr; 
    } 
    if (scanf("%d", &m) != 1) 
     return 1; 
    for (ptr = head, i = 0; i < m; i++) { 
     if (scanf(" %d", &x) != 1) 
      return 1; 
     while (ptr && x > ptr->score) 
      ptr = ptr->next; 
     if (ptr == NULL) 
      rank = 1; 
     else 
     if (x == ptr->score) 
      rank = ptr->rank; 
     else 
      rank = ptr->rank + 1; 
     printf("%d\n", rank); 
    } 
    return 0; 
}