题解 P2782 【友好城市】

· · 题解

其实这个题总结一下规律，就可以发现，将北岸的城市排好序，求出南岸城市的最长不下降序列，就是最后的结果。那么这个题，如果用n^2的方法话，应该能过几个点，但是过不了全部的点，会tle。那么就考虑一下nlogn。nlogn的算法，突破点在于二分查找。那么思路是什么样的呢？ 假定有一个序列：3 2 6 9 4 7 8

那么i=1时，只有3，加入序列，f[1]=3。

i=2，2肯定不能直接加入后面，但是如果用2把3给替换掉，很明显结果不会更差，那么用2把3替换掉。

i=3和4，6和9都可以直接加入后面。

i=5，把他替换掉6，虽然打眼一看不符合要求，可是这样替换不会导致更差的结果，还更有可能变好。

i=6，如果用7把9给替换掉，是否会更好呢？答案是肯定的，思路与i=5时一样。

i=7，8可以直接加入后面。这时候有没有发现，如果不去替换9，是不是结果就不是最优了。

最后，代码奉上：

#include <iostream>
#include <algorithm>
using namespace std;
int n,f[200000],ans,len;
struct st{
    int nor,sou;
}city[200000];
bool cmp(st x,st y)//结构体排序函数
{
    return x.nor<y.nor;
}
int main(){
    cin >> n;
    for(int i=1;i<=n;i++)
    {
        cin >>city[i].nor>> city[i].sou;
    }
    sort(city,city+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        int a=city[i].sou;
        //cout<<a<<":";
        len=upper_bound(f+1,f+len+1,a)-f;
        //printf("%d,%d\n",i,len);
        f[len]=a;
        ans=max(ans,len);
    }
    cout << ans;//去掉+1。。。
    return 0;
}

管理大大求过~~