0

私はこの練習問題を解決しようとしていましたが、以下にも引用されています。

シェフは、DirectiPlex の就任式パーティーのビュッフェを計画しており、全員が招待されています。途中で、各ゲストは乱数 (この番号は繰り返される場合があります) が書かれた紙を受け取ります。その後、ゲストは友人と一緒に円卓に座ります。シェフは、ゲームをプレイすることにしました。彼はあなたのテーブルから無作為に人を選び、彼らの番号を声に出して読んでもらうように頼みます. 次に、テーブルの周りを時計回りに移動し、各人が自分の番号を読み上げます。目標は、増加する部分列を形成する数のセットを見つけることです。これらの番号を所有しているすべての人は、ラッキー ドローの対象となります。ソフトウェア開発者の 1 人は、この見通しに非常に興奮しており、ラッキー ドローの対象となる人の数を最大化したいと考えています。そう、彼は、くじ引きの対象となる人数を最大化するために、誰が最初に自分の番号を読むべきかを決定するプログラムを作成することにしました。彼を打ち負かすことができますか？入力 最初の行には、テスト ケースの数 (約 15) である t が含まれます。次に、t 個のテスト ケースが続きます。各テスト ケースは次の 2 行で構成されます。

最初の行には、パーティーに招待されたゲストの数 N が含まれています。

2行目には、スペースで区切られたN個の数字a1、a2、...が含まれています。これらは、紙に時計回りに書かれた数字です。出力 テスト ケースごとに、抽選に参加できるゲストの最大数である 1 つの数字を含む行を出力します。

これが私が思いついた解決策です

// http://www.codechef.com/problems/D2/
import java.io.*;
import java.util.*;

public class D2
{
  public static void main(String [] args)
    throws IOException
  {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int numTestCases = Integer.parseInt(br.readLine());
    for(int _t=0; _t<numTestCases; ++_t)
    {
      int N = Integer.parseInt(br.readLine());
      StringTokenizer strtok = new StringTokenizer(br.readLine());
      int [] originalArray = new int[N*2];
      for(int i=0; i<N; ++i)
      {
        //this concatenates the array with itself at the time of reading the input itself
        originalArray[i] = originalArray[N+i] = Integer.parseInt(strtok.nextToken());
      }
      //Now we calculate the length of the longest increasing sequence
      int maxWinners = new LongestIncreasingSequence(originalArray).lengthOfLongestIncreasingSequence();
      System.out.println(maxWinners);
    }
  }
}

class LongestIncreasingSequence
{
  private int [] array;
  private int [] longest;
  private int subsequence_size;
  public LongestIncreasingSequence(int [] A)
  {
    array = A;
    longest = new int[array.length / 2];
    longest[0] = array[0];
    subsequence_size = 1;
  }

  public int lengthOfLongestIncreasingSequence()
  {
    for(int i=1; i<array.length; ++i)
    {
      if(array[i] < longest[0])
      {
        longest[0] = array[i];
      }
      else if(array[i] > longest[subsequence_size - 1])
      {
        longest[subsequence_size++] = array[i];
      }
      else
      {
        //Make the replacement with binary search
        longest[getReplacementIndex(array[i])] = array[i];
      }
    }
    return subsequence_size;
  }

  //Method to find the correct index using binary search
  private int getReplacementIndex(int elem)
  {
    int left, right, mid;
    left = 0; right = subsequence_size - 1;
    while(right - left > 1)
    {
      mid = 1 + (right - left) / 2;
      if(array[mid] >= elem)
      {
        if(mid != right) right = mid;
        else --right;
      }
      else
      {
        left = mid;
      }
    }
    return right;
  }
}

複雑なのはO(n(log(n))、配列をそれ自体と連結して、最長増加シーケンスを見つけていることです。

ただし、これは時間要件を満たしません。誰かがこの実装をスピードアップするのを手伝ってくれますか?

4

1 に答える 1

1

ローテーションは行いませんNが、代わりに、最長の (サイクリック) 実行を一度に決定します。それは確かに実行可能です。配列の最後でワープするように注意する必要があります。

于 2012-05-22T12:47:39.767 に答える