算法至美

用户名：uq_54514514336

访问量：7734

签　名：

等　　级
排　　名	1360
经　　验	2948
参赛次数	0
文章发表	43
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

信息学奥赛一本通T1541-数列区间最大值-题解（C++代码）
浏览：262

信息学奥赛一本通T1547-区间和-题解（C语言代码）
浏览：324

信息学奥赛一本通T1656-Combination-题解（各语言代码）
浏览：181

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言训练-阶乘和数* （C++代码）（直接输出样例hhhh）

信息学奥赛一本通T1264-合唱队形-题解（各语言代码）

　　作者: 算法至美　　　　发表时间：2022-06-27 19:39:13 浏览：217　|　评论：0　

原题链接：信息学奥赛一本通T1264-合唱队形

从正向和反向分别求出最长上升子序列，然后两者相加
得到结果的最大值减一，就等于队形人数的最大值
总人数减去队形人数的最大值，就是最少出列人数
时间复杂度$$O(n\log n)$$，空间复杂度$$O(n)$$
**python**
```python
from bisect import bisect_left
def f(x):
	l=[float('inf')]
	for i in x:
		if i>l[-1]:l.append(i)
		else:l[bisect_left(l,i)]=i
		yield len(l)
print(int(input())-~-max((lambda t:map(int.__add__,tuple(f(t))[::-1],f(t[::-1])))(tuple(map(int,input().split())))))
```
**C++**
```cpp
#include<vector>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
	int n;
	cin>>n;
	int*a=new int[n],*b=new int[n];
	for(int i=n;i--;cin>>a[i]);
	vector<int>v(1,*a);
	for(int i=0;i!=n;b[i++]=v.size())
		if(a[i]>v.back())v.push_back(a[i]);
		else*lower_bound(v.begin(),v.end(),a[i])=a[i];
	v=vector<int>(1,a[~-n]);
	for(int i=n;i--;b[i]+=v.size())
		if(a[i]>v.back())v.push_back(a[i]);
		else*lower_bound(v.begin(),v.end(),a[i])=a[i];
	cout<<n-~-*max_element(b,b+n);
}
```
**java**
```java
import java.util.Arrays;
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
	public static void main(String[] args) {
		final Scanner in = new Scanner(System.in);
		final int n = in.nextInt();
		final int[] a = new int[n], b = new int[n];
		for (int i = n; i-- != 0; a[i] = in.nextInt());
		ArrayList<Integer> p = new ArrayList<>(), q = new ArrayList<>();
		in.close();
		q.add(a[0]);
		p.add(a[~-n]);
		for (int i = n; i-- != 0; i = n+~i) {
			if (a[i] > p.get(~-p.size())) p.add(a[i]);
			else p.set(Math.abs(Collections.binarySearch(p, a[i]) << 1 | 1) >> 1, a[i]);
			b[i] += p.size();
			if (a[i = n+~i] > q.get(~-q.size())) q.add(a[i]);
			else q.set(Math.abs(Collections.binarySearch(q, a[i]) << 1 | 1) >> 1, a[i]);
			b[i] += q.size();
		}
		System.out.print(n-~-Arrays.stream(b).max().getAsInt());
	}
}
```

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

算法至美

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言考试练习题_排列（C++代码）

C语言训练-阶乘和数* （C++代码）（直接输出样例hhhh）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

信息学奥赛一本通T1264-合唱队形-题解（各语言代码）

评论区

精彩推荐

C语言考试练习题_排列（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

Cylinder （C语言描述，蓝桥杯）

星期判断机（C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

整数平均值（C语言代码）

1134题解(求分析)

算法至美

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题6.11 （C语言代码）

C语言考试练习题_排列 （C++代码）

C语言训练-阶乘和数* （C++代码）（直接输出样例hhhh）

点我有惊喜！你懂得！

C语言程序设计教程（第三版）课后习题7.5 （C语言代码）

信息学奥赛一本通T1264-合唱队形-题解（各语言代码）

评论区

精彩推荐

C语言考试练习题_排列 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

Cylinder （C语言描述，蓝桥杯）

星期判断机 （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

整数平均值 （C语言代码）

1134题解(求分析)

C语言考试练习题_排列（C++代码）

　　评论区

C语言考试练习题_排列（C语言代码）

星期判断机（C语言代码）

整数平均值（C语言代码）