题解 P2782 【友好城市】

铃宕 · 2018-11-09 21:05:27 · 题解

居然这么多题解都没有桶排，桶排好像好理解很多啊。

a[i]表示南岸第i个城市的友好城市是a[i],那就从1到最大的城市坐标循环一次，建个数组b存储北岸城市的坐标顺序，不就排好序了吗。

代码：

for(int i=1;i<=n;i++){
    cin>>x;
    cin>>a[x];
    maxn=max(maxn,a[x]);
}
for(int i=0;i<=maxn;i++){
    if(a[i]){
        ans++;
        b[ans]=a[i];
    }
}

再求b的最长上升子序列的长度就好了（nlogn的算法我用的是二分，不过lower_bound简单一些）

AC代码：

#include<bits/stdc++.h>
using  namespace std;
int n,a[200020],b[1000020],f[200020],x,ans,l,r,mid,maxn;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        cin>>a[x];
        maxn=max(maxn,a[x]);
    }
    for(int i=0;i<=maxn;i++){
        if(a[i]){
            ans++;
            b[ans]=a[i];
        }
    }
    ans=0;
    for(int i=0;i<=n;i++)f[i]=-1;
    for(int i=1;i<=n;i++){
        if(f[ans]<b[i])f[++ans]=b[i];
        else{
            l=0;r=ans;
            while(l<r){
                mid=(l+r)/2;
                if(f[mid]>=b[i])r=mid;
                else l=mid+1;
            }
            f[l]=b[i];
        }
    }
    cout<<ans;
}