AcWing 482. 合唱队形
原题链接
中等
作者:
叶忖
,
2021-01-29 16:58:00
,
所有人可见
,
阅读 338
二分
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
public class Main {
private static int n;
private static int[] T, f, g;
private static BufferedReader reader;
private static PrintWriter writer;
public static void main(String[] args) throws IOException{
reader = new BufferedReader(new InputStreamReader(System.in));
writer = new PrintWriter(System.out);
n = Integer.parseInt(reader.readLine());
String[] s = reader.readLine().split(" ");
reader.close();
T = new int[n + 1]; f = new int[n + 1]; g = new int[n + 1];
for (int i = 1; i <= n; i ++) {
T[i] = Integer.parseInt(s[i - 1]);
}
int res = 0;
for (int i = 1; i <= n; i ++) {
int idx1 = 1, idx2 = 1;
f[idx1] = T[1];
g[idx1] = T[n];
// 处理左边
for (int j = 2; j <= i; j ++) {
if (T[j] > f[idx1]) f[ ++ idx1] = T[j];
else {
int index = lower_bound(f, T[j], idx1);
f[index] = T[j];
}
}
// 处理右边
for (int j = n - 1; j >= i; j --) {
if (T[j] > g[idx2]) g[ ++ idx2] = T[j];
else {
int index = lower_bound(g, T[j], idx2);
g[index] = T[j];
}
}
res = Math.max(res, idx1 + idx2 - 1);
}
writer.print(n - res);
writer.flush();
writer.close();
}
private static int lower_bound(int[] nums, int x, int len) {
int l = 1, r = len;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] < x) l = mid + 1;
else r = mid;
}
return l;
}
}