P6763 解题报告

· · 题解

前言

题目链接，个人博客内食用更佳。

思路分析

我们优先考虑两条线段不相交的条件是什么：

如图，可以得到是：

x_{i1}<x_{j1} and x_{i2}<x_{j2}

所以题目就被转化成了一个二维偏序问题。

首先考虑用按第一个坐标排序的方法去掉一维。

接着根据 Dilworth 定理可以把题目转化为一个求第二维的最长上升子序列的问题。

不会 Dilworth 定理的戳这里看第二问。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct node{int x,y;}a[100010];
int n,dt,pos;
int q[100010];
static char buf[1000000],*paa=buf,*pd=buf;
#define getchar() paa==pd&&(pd=(paa=buf)+fread(buf,1,1000000,stdin),paa==pd)?EOF:*paa++
inline int read(void){
    int x(0),t(1);char fc(getchar());
    while(!isdigit(fc)){if(fc=='-') t=-1;fc=getchar();}
    while(isdigit(fc)) x=(x<<1)+(x<<3)+(fc^48),fc=getchar();
    return x*t;
}
inline void print(int x)
{
    if(x<0) putchar('-'),x=-x;
    if(x>9) print(x/10);
    putchar(x%10+'0');
}
bool cmp(node x,node y){return x.x<y.x;}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read();
    sort(a+1,a+1+n,cmp);q[++dt]=a[1].y;
    for(int i=2;i<=n;i++)
        if(a[i].y<q[dt]) q[++dt]=a[i].y;
        else
        {
            int pos=dt,l=1,r=n;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(a[i].y>=q[mid]) pos=min(pos,mid),r=mid-1;
                else l=mid+1;
            }
        q[pos]=a[i].y;
    }
    print(dt);
    return 0;
}