合唱队

描述 知识点 运行时间限制 内存限制 输入 输出 样例输入 样例输出

计算最少出列多少位同学，使得剩下的同学排成合唱队形

说明：

N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。 
合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1，2…，K，他们的身高分别为T1，T2，…，TK，   则他们的身高满足存在i（1<=i<=K）使得Ti<T2<......<Ti-1<Ti>Ti+1>......>TK。 
     你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 

 

 

循环

0M

0

整数N

一行整数，空格隔开，N位同学身高

 

最少需要几位同学出列

8 186 186 150 200 160 130 197 200

4

package huawei.copy;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int count = scanner.nextInt();
		int[] arr = new int[count];
		for (int i = 0; i < count; i++) {
			arr[i] = scanner.nextInt();
		}
//		System.out.println(Arrays.toString(arr));
		/*int[] arr = new int[]{186,186, 150, 200, 160, 130, 197, 200};*/
		System.out.println(solve(arr));
	}
	private static int solve(int[] array) {
		int max = 0;
		for (int i = 1; i < array.length; i++) {
			int[] part1 = Arrays.copyOfRange(array, 0, i);
			int[] part2 = Arrays.copyOfRange(array, i, array.length);
			reverse(part2);
//			System.out.println(Arrays.toString(part2));
			int len1 = solve2(part1);
			int len2 = solve2(part2);
			if (len1+len2 > max) {
				max = len1+len2;
			}
		}
		return array.length-max;
	}
	
	private static void reverse(int[] part2) {
		for (int start = 0, end=part2.length-1; start < end; start++, end--) {
			int t = part2[start];
			part2[start] = part2[end];
			part2[end] = t;
		}
	}

	private static int solve2(int[] nums) {
		//o(n*logn)
		int[] LIS = new int[nums.length+1];
		LIS[1] = nums[0];
		int len = 1;
		for (int i = 1; i < nums.length; i++) {
			int pos = findPos(LIS, 1, len, nums[i]);
			LIS[pos] = nums[i];
			if (len < pos) {
				len = pos;
			}
		}
		return len;
	}
	private static int findPos(int[] lIS, int s, int e, int key) {
		if (key > lIS[e]) {
			return e+1;
		}
		while (s <= e) {
			int mid = s+(e-s)/2;
			if (lIS[mid] > key) {
				e = mid-1;
			} else if (lIS[mid] < key){
				s = mid+1;
			} else {
				return mid;
			}
		}
		return s;
	}
}