题解byliguanghan1

这道题的题目看似很吓人，其实是废话。

整理题目：

一条河从东向西流过，河的两岸各有n个城市，且北岸的每一个城市都与南岸的某个城市是友好城市，而且对应的关系是一一对应的。现在要求在两个友好城市之间建立一条航线，但为了安全起见，所有航线都不能相交，因此，不是所有的友好城市都能建立航线。 请问最多能建多少航线？

整理后：

两条平行的线段上各有n个点，每两个点互相对应。连接每两个对应的点，线段间不能相交。求可连接线段最大值。

这样，我们就把一个复杂的情景题变为了一道模板题。 为什么呢？ 这样，我们就把一个复杂的情景题变为了一道模板题。 为什么呢？ 仔细观察这个图，可以发现线段的最大数量正是排序一边后另一边的最长不下降子序列的长度。仔细观察这个图，可以发现线段的最大数量正是排序一边后另一边的最长不下降子序列的长度。

而最长不下降子序列不就是模板吗？

代码如下：

珍爱生命，拒绝抄袭

#include<stdio.h>
#include<algorithm>
using namespace std;
struct node
{
  int north，south;
}a[200005];
int n,i,d[200005],len,temp,f1,f2;
bool cmp(node x,node y)
{
  return x.north<y.north;
}
//定义都看得懂吧
int main ()
{
  scanf("%d%d",&f1,&f2);//其实长和宽没用，数据肯定是符合要求的
  scanf("%d",&n);
  for(i=1; i<=n; i++)
    scanf("%d%d",&a[i].north,&a[i].south);//以上是输入
  sort(a+1,a+1+n,cmp);//对北边排序（万能的sort）
  //下面是STL二分的模板
  d[++len]=a[1].south;
  for(i=2; i<=n; i++)
  {
    int ll=upper_bound(d+1,d+len+1,a[i].south)-d;
    d[ll]=a[i].south;
    if(ll>len)
      len++;
  }
  printf("%d",len);
  return 0;//完美结束
}

你学废了吗