自动搬运

查看原文

来自洛谷，原作者为

	1379号监听员 Every thing that downs me makes me wanna fly

搬运于2025-08-24 21:41:34，当前版本为作者最后更新于2019-04-09 22:53:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解

条件分析

首先，我们分析一下航道不交叉的条件。

如果有一条已经被批准的航道，南北坐标为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，从前往后扫描；

1. 扫描到100，将100加入序列
2. 扫描到389，将389加入序列尾部
3. 扫描到207，将207替换掉389（因为它更小，可以让更多数插进来）
4. 扫描到99，将99替换掉100（这不会使结果变差）
5. 扫描到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;
 } 

————写小白也能看懂的题解！