能帮忙调一下吗(10分(还是个小学生,十分蒟蒻)?谢谢!
查看原帖
能帮忙调一下吗(10分(还是个小学生,十分蒟蒻)?谢谢!
766225
wulinxi101楼主2023/12/4 11:35
#include <iostream>
#include <algorithm>
using namespace std;
int n, a[100010], b[100010], id[100010];
int f[100010], cnt = 0;
int search(int l, int r, int d)
{
	while(l < r)
	{
	    int mid = (l + r) / 2;
	    if(f[mid] >= d) r = mid;
	    else l = mid + 1;
	}
	return l;
}
int main()
{
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) cin >> b[i];
	for(int i = 1; i <= n; i++) id[a[i]] = i;//重定义顺序
	for(int i = 1; i <= n; i++) b[i] = id[b[i]];
	//在b[i]中找最长上升子序列
	for(int i = 1; i <= n; i++)
	{
		if(a[i] > f[cnt]) f[++cnt] = a[i];
		else
		{
			//找到第一个大于f[i]的
			int pos = search(1, cnt, a[i]);
			f[pos] = a[i];
		}
	}
	cout << cnt;
	return 0;
}
2023/12/4 11:35
加载中...