题解 P2782 【友好城市】

题解

条件分析

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

如果有一条已经被批准的航道,南北坐标为N1,S1;

则第二条N2<N1,S2>S1(或恰好相反)的航道将不能被批准,因为他们发生了交叉。


参照此图:

1
2
3
4
5
6
7
8
9
.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,效率很高(其实就是二分查找)。


贴代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

#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;
}

————写小白也能看懂的题解!
文章作者: 1379号监听员
文章链接: https://listener1379.site/2019/题解-P2782-【友好城市】/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 1379号监听站
支付宝打赏
微信打赏