0

我试图解决这个实践问题，下面也引用了它。

主厨正在为 DirectiPlex 就职派对策划自助餐，并邀请了所有人。在他们进来的路上，每位客人都会拿起一张纸，里面有一个随机数字（这个数字可能会重复）。客人们随后与他们的朋友坐在圆桌旁。厨师现在决定他想玩一个游戏。他让你从你的桌子上随机挑选一个人，让他们大声读出他们的号码。然后，围绕桌子顺时针移动，每个人都会读出他们的号码。目标是找到形成递增子序列的那组数字。所有拥有这些号码的人都将有资格参加幸运抽奖！一位软件开发人员对此前景感到非常兴奋，并希望最大限度地增加有资格参加幸运抽奖的人数。所以，他决定编写一个程序来决定谁应该先读取他们的号码，以最大限度地增加有资格参加幸运抽奖的人数。你能打败他吗？Input 第一行包含 t，测试用例的数量（大约 15 个）。然后是 t 个测试用例。每个测试用例由两行组成：

第一行包含一个数字 N，即被邀请参加聚会的客人人数。

第二行包含 N 个数字 a1, a2, ...，一个以空格分隔的数字，它们是按顺时针顺序写在纸上的数字。输出 对于每个测试用例，打印一行包含一个数字，该数字是有资格参加幸运抽奖的客人的最大数量。

这是我想出的解决方案

// 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 回答