解析

通过画图分析不难得到：首先我们对其中一个河岸从小到大排序，然后在另一个河岸中求出最长上升自序列即可。为什么这么写呢？因为爱情 因为所有合法的答案都是一个单调上升队列。
以下是代码：
#include<cstdio>
#include<algorithm>
using namespace std;
struct river{
int sou,nor;
}a[10000001];
int n;
int ans[1000001];
int tot = 1;
bool cmp(river x,river y){
return x.nor < y.nor;
}
int main ()
{
scanf("%d" ,&n);
for(int i = 1;i <= n; i++){
scanf("%d %d" ,&a[i].nor,&a[i].sou);
}
sort(a + 1,a + 1 + n,cmp);
ans[tot] = a[tot].sou;
for(int i = 2;i <= n; i++){
if(a[i].sou > ans[tot]){
tot++;
ans[tot] = a[i].sou;
}
if(a[i].sou < ans[tot]){
int pl = upper_bound(ans + 1,ans + 1 + tot,a[i].sou) - ans;
ans[pl] = a[i].sou;
}
}
printf("%d" ,tot);
return 0;
}

题解：友好城市

原文：https://www.cnblogs.com/Crazyman-W/p/14691275.html