|
计算最少出列多少位同学，使得剩下的同学排成合唱队形 说明： N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。? ? ? |
| 循环 |
| 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;
}
}
?
原文：http://hcx2013.iteye.com/blog/2236947