P2782 友好城市题解

· · 题解

对于任意长度得最长上升子序列，只需要存储最大值最小得那一个序列即可。例如： 

长度为2得上升子序列有:
1, 2
4, 6
显然对于要求长度为3得上升子序列，接在1，2这个子序列后面要更容易，而接在4，6这个子序列后面要更难，
因此对于任意长度得最长子序列，只需要存储最大值最小的那个子序列即可。

首先对于所有友好城市按南岸的坐标从小到大排序。 假设现在选了批准了第一对友好城市，那么从2 ~ n对友好城市想要建成，那么北岸城市的坐标必须 要大于第一队友好城市的北岸坐标。依次类推，发现其实北岸的坐标最终会构成一个单调上升的子序 列，因此最多有多少对友好城市可以批准其实就是在找此时的最长上升子序列。

代码： 

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=2e5+10;
struct Node{
    int x,y;
}a[N];
int f[N],idx;// f[i]记录上升子序列长度为i时，最大值最小是多少

bool cmp(Node u,Node v)
{
    return u.x<v.x;
}
signed main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
        cin>>a[i].x>>a[i].y;
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;++i)
    {
        int l=0,r=idx;
        while(l<r)
        {
            int mid=(l+r+1)>>1;
            if(f[mid]<a[i].y) l=mid;
            else r=mid-1;
        }// 想要找到以i结尾的最长上升子序列，那么就需要找到小于a[i].y的最大值的最长上升子序列是多长
        idx=max(idx,l+1);// 判断a[i].y是否大于所有值，如果是的，那么此时第i个数可以添加到最后，可以组成idx + 1长度的最长上升子序列
        if(f[l+1]>a[i].y || !f[l+1])// 判断长度为l + 1的最长上升子序列中最大值的最小是否是i
            f[l+1]=a[i].y;
    }
    cout<<idx<<"\n";
    return 0;
}