30分求助
查看原帖
30分求助
602282
huangguoguo楼主2022/1/12 11:26

用的是离散化的方法,但始终没发现wa在哪里,求助!

#include <bits/stdc++.h>
using namespace std;
const int MAX=100005;
map<int,int> mp;
int a[MAX];
int b[MAX];

int main() {
	int n;
	cin>>n;
	for (int i=1;i<=n;i++) {
		int x;
		cin>>x;
		mp[i]=x;
	}
	for (int i=1;i<=n;i++) {
		int x;
		cin>>x;
		a[i]=mp[x];
	}
	b[1]=a[1];
	int idx=1;
	for (int i=2;i<=n;i++) {
		if (a[i]>b[idx]) {
			idx++;
			b[idx]=a[i];
		}
		else {
			int p=upper_bound(b+1,b+1+idx,a[i])-b;
			b[p]=a[i];
		}
	} 
	cout<<idx<<endl;
	return 0;
}
2022/1/12 11:26
加载中...