LonginusMonkey @ 2022-08-10 22:47:22
向大佬求助!
#include<bits/stdc++.h>
using namespace std;
int arr2[100010];
struct node{
int a, b;
};
node arr[100010];
vector<int> vec;
bool cmp(node a, node b) {
return a.a < b.a;
}
int main() {
int n;
cin >> n;
for(int i=1; i<=n; ++i) {
cin >> arr[i].a;
}
for(int i=1; i<=n; ++i) {
cin >> arr[i].b;
}
sort(arr+1,arr+1+n,cmp);
for(int i=1; i<=n; ++i) {
arr2[i] = arr[i].b;
}
vec.push_back(arr2[1]);
for(int i=2; i<=n; ++i) {
if(arr2[i] > vec[vec.size()-1]) {
vec.push_back(arr2[i]);
}
else
{
int u = lower_bound(vec.begin(),vec.end(),arr2[i])-vec.begin();
vec[u] = arr2[i];
}
}
cout << vec.size();
return 0;
}
by songtj @ 2022-09-11 11:08:24
这道题排序再一个个比对是不行的,要离散化一下,然后就可以变成求最长上升子序列了
可以看一下这个dalao的题解:
链接
这个dalao讲了原理:
链接