算法至美

用户名：uq_54514514336

访问量：7733

签　名：

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

　　自我简介：

TA的其他文章

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

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

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

你可能喜欢

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

信息学奥赛一本通T1260-拦截导弹-题解（各语言二分法）

　　作者: 算法至美　　　　发表时间：2022-06-25 23:13:40 浏览：130　|　评论：0　

原题链接：信息学奥赛一本通T1260-拦截导弹

最长上升子序列
时间复杂度$$O(n\log n)$$
**python**
```python
from bisect import bisect_left
t,*l=map(int,input().split())
p,q=[t],[~t]
for i in l:
	if i>p[-1]:p.append(i)
	else:p[bisect_left(p,i)]=i
	i=~i
	if i<q[-1]:q[bisect_left(q,i)]=i
	else:q.append(i)
print(len(q))
print(len(p))
```
**C++**
```cpp
#include<vector>
#include<iostream>
using namespace std;
int main(){
	int i;
	cin>>i;
	vector<int>p(1,i),q(1,~i);
	while(cin>>i){
		if(i>p.back())p.push_back(i);
		else*lower_bound(p.begin(),p.end(),i)=i;
		i=~i;
		if(i<q.back())*lower_bound(q.begin(),q.end(),i)=i;
		else q.push_back(i);
	}
	cout<<q.size()<<endl<<p.size();
}
```
**java**
```java
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 ArrayList<Integer> p = new ArrayList<>(), q = new ArrayList<>();
		int i = in.nextInt();
		p.add(i);
		q.add(~i);
		while (in.hasNext()) {
			i = in.nextInt();
			if (i > p.get(~-p.size())) p.add(i);
			else p.set(Math.abs(Collections.binarySearch(p, i) << 1 | 1) >> 1, i);
			i = ~i;
			if (i < q.get(~-q.size())) q.set(Math.abs(Collections.binarySearch(q, i) << 1 | 1) >> 1, i);
			else q.add(i);
		}
		in.close();
		System.out.println(q.size());
		System.out.println(p.size());
	}
}
```

0.0分

0 人评分

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

算法至美

TA的其他文章

你可能喜欢

C二级辅导-求偶数和（C语言代码）

三进制小数（C语言代码）

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

C二级辅导-等差数列（C语言代码）

点我有惊喜！你懂得！

信息学奥赛一本通T1260-拦截导弹-题解（各语言二分法）

评论区

精彩推荐

小九九（C语言代码）

矩形面积交（C语言代码）

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

用筛法求之N内的素数。（C语言代码）

简单的a+b （C语言代码）

C语言训练-大、小写问题（C语言代码）

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

A+B for Input-Output Practice (VI) （C语言代码）

Pascal三角（C语言代码）

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

算法至美

TA的其他文章

你可能喜欢

C二级辅导-求偶数和 （C语言代码）

三进制小数 （C语言代码）

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

C二级辅导-等差数列 （C语言代码）

点我有惊喜！你懂得！

信息学奥赛一本通T1260-拦截导弹-题解（各语言二分法）

评论区

精彩推荐

小九九 （C语言代码）

矩形面积交 （C语言代码）

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

用筛法求之N内的素数。 （C语言代码）

简单的a+b （C语言代码）

C语言训练-大、小写问题 （C语言代码）

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

A+B for Input-Output Practice (VI) （C语言代码）

Pascal三角 （C语言代码）

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

C二级辅导-求偶数和（C语言代码）

三进制小数（C语言代码）

C二级辅导-等差数列（C语言代码）

　　评论区

小九九（C语言代码）

矩形面积交（C语言代码）

用筛法求之N内的素数。（C语言代码）

C语言训练-大、小写问题（C语言代码）

Pascal三角（C语言代码）