渡轮问题

发布于 2019-04-06  858 次阅读


题目描述

Palmia河在某国从东向西流,并把该国分成南北两个部份。河的两岸共有n个城市,且北岸的某个城市与南岸的某个城市是友好城市,而且对应的关系是一一对应。如下图:
这里写图片描述
现要求在两个友好城市之间建立一条航线,但由于天气关系,所有的航线都不能相交,因此就可能所有城市都建立航线。如上图,则最多可建立两条航线可保证航线不交叉。

输入

第一行为一个数n(n<=5000),表示城市的个数。第二行为n个数,表示南边n个城市离河的源头的距离(小于2^31-1)。第三行为n个数,表示北边n个城市离河的源头的距离(<2^31-1),距离为整数。

输出

一个数,能建立最多的航线。

思路

其实就是将前一个排序,后一个做一边最长不下降子序列

#include
using namespace std;
int a[50000],d[50000],b[50000];
__attribute__((optimize("O2")))
int ef(int f,int k)
{
    int l=1,r=k,mid;
    while(l<=r)
    {
        mid=(l+r)/2;
        if(d[mid]==f)   return mid;
        if(d[mid]f)    r=mid-1;
    }
    return l;
}
__attribute__((optimize("O2")))
void quick_sort(int a[],int left,int right)  
{  
    if(leftx)  
            j--;  
        if(ilen)   len=c;
    }
    printf("%d",len);   
}
]]>