题解 P2782 【友好城市】
题解
条件分析
首先，我们分析一下航道不交叉的条件。
如果有一条已经被批准的航道，南北坐标为N1,S1;
则第二条N2<N1,S2>S1（或恰好相反）的航道将不能被批准，因为他们发生了交叉。
参照此图：
.N .N
\ |
\ |
\ |
\|
|
|\
| \
.S .S因此，要满足题目中的条件，需要保证南岸序列和北岸序列单调上升（题目中交代了坐标不会重合）。
我们可以按北岸坐标大小对城市进行排序，来保证北岸序列单调上升；
然后，南岸序列的最长上升子序列长度就是能够批准的航线条数。
最长上升子序列
如何求出最长上升子序列的长度？
不难看出，这个问题用动态规划解决会很简单，
边界为f(1)=1
状态转移方程为f(i)=max{f(i),f(j)+1|S(i)>s(j)} (i=1,i<=n) (j=i+1,j<=n)
然而 这题的数据规模。。。 n<=200000;
n方的动态规划肯定TLE，我们得想点别的办法。
假设有一个序列 100 389 207 99 300，从前往后扫描；
- 扫描到100，将100加入序列
- 扫描到389，将389加入序列尾部
- 扫描到207，将207替换掉389（因为它更小，可以让更多数插进来）
- 扫描到99，将99替换掉100（这不会使结果变差）
- 扫描到300，加入序列尾部（可以看出，如果不执行第三步的替换，这里会漏过最优解）
因此，我们的策略是：如果当前数比序列尾更大，直接将其插入尾部，序列长度+1；
否则用它替换掉序列中比它大但又最小的一个（保持单调性）。
对于情况一，可在常数时间内完成；
对于情况二，STL中有现成的函数——lower_bound（这题upper_bound也可以），他的时间复杂度是logn，效率很高（其实就是二分查找）。
贴代码：
#include<iostream>
#include<algorithm>
using namespace std;
struct city{
//方便排序
int north;//北岸
int south;//南岸
};
struct cmp{
bool operator () (city& a,city& b)
{
return a.north<b.north;
}
};
city c[200005];
int lis[200005];//LIS序列
int ans=0;//LIS长度
int n;
int main()
{
ios::sync_with_stdio(false);//流式I/O加速
cin.tie(0);
cin>>n;
for(int i=1;i<=n;++i)
{
cin>>c[i].north>>c[i].south;
}
sort(c+1,c+n+1,cmp());//将城市按北岸排序，之后就没北岸什么事了
for(int i=1;i<=n;i++)
{
if(c[i].south>lis[ans])//如果能插入
{
lis[++ans]=c[i].south;//插入至末尾
}
else
{
//否则二分查找出序列中比它大但又最小的一个并替换
*lower_bound(lis+1,lis+ans+1,c[i].south)= (c[i].south);
}
}
cout<<ans<<endl;
return 0;
}