SPOJ：一般（期限超過）

Question

私はこの単純な問題（http://br.spoj.com/problems/GENERAL/）をspojでかなりの間解決しようとしていましたが、何らかの理由でTLE（時間制限を超過）を取得し続けます。

問題はポルトガル、問題の簡単な説明であるので、（話なし）このようなものです：あなたは、サイズNの配列を与えられている

、あなたはの配列を配置する必要があり要素のみそこから距離Kである 要素と交換することができるように 昇順。配列は、それが印刷impossivelをソートすることができない場合は、 昇順でそれらを配置するために必要なスワップの数を印刷し、その後 をソートすることができます。

これは私のコードです::

#include <iostream> 
#include <cstdio> 

using namespace std; 
int a[100005]; 
int main() { 
    int t; 
    int n, k; 
    scanf("%d", &t); //number of test cases 
    while(t--) { 
     scanf("%d %d", &n, &k); 
     bool result = true; 
     int count = 0; 

     for(int i = 0; i < n; i++) { 
      scanf("%d", &a[i]); 
     } 

     for(int i = n; i > 0; i = i - k) { 
      int j = 0; 
      for(; j < i - k; j++) { 
       if(a[j] > a[j + k]) { 
        int temp = a[j]; 
        a[j] = a[j + k]; 
        a[j + k] = temp; 
        count++; 
       } 
      } 

      for(; j < i - 1; j++) { 
       if(a[j] > a[j + 1]) { 
        result = false; 
        break; 
       } 
      } 

      if(!result) 
       break; 
     } 
     if(result) 
      printf("%d\n", count); 
     else 
      printf("impossivel\n"); 
    } 
} 

私のロジック：私は、アレイ上のの反復N/Kを実行します。ループ変数を初期化する〜N各反復では、私はそれからの距離Kの要素を持つI-kの要素をチェックし、彼らはその後、交換することになっている場合、私は、私は何もしない他に、それらを交換し、必要なスワップの数を増加させます。彼らは昇順である場合、私は他に、ループやプリント「impossivel」を壊さないなら、私はにI-kのから要素をチェックし、私はループを実行し、再び私にI-Kとを変更します。すべての反復の後で私のロジックによって、最後のk要素は、すべてのステップで右に大きい要素を移動するので、並べ替えることが可能であれば、昇順になります。

これはあなたに正しいように見えるのか？これをさらに最適化するには？事前に助けてくれてありがとう。 :)

Answer 1

それぞれn/k要素のk個のサブリストに分かれています。

確認不可状態。

不能状態

1（K = 2、

3 4 1 2は、n/k個のリストの配列

番号がOに存在するかどうかを確認するために配列を維持されてみましょう）。

たとえば、 2

の離間間隔で我々は2つのサブリスト、3 1、4 2 に分けることができる今はソートが

1 2 3 4（1及びn O（N）との間の高さとして使用カウントソート）知っています

そこで、我々は最初の場所で1を期待しています。さあ、ここに来てもいい？それがサブリストにある場合のみ。[Y]

我々は引き続き他の行われてい不可能ならば[N]は

"不可能" と言うなら

。

k倍は、K * N/K（ログ（N/K））が

（反転回数が配列[知らプロパティ] をソートする隣接スワップの最小数に等しい、ソートマージ参照してください：アプローチの Sorting a sequence by swapping adjacent elements using minimum swaps ）

複雑さがnのnログインされ、容易に通過あろう:)あなたはおそらく、[コードレビュー]（HTTP上の優れたレスポンスの投稿があります