AT_abc463_d 题解

· · 题解

比较有意思的一个题。

不过我可能做复杂了，但不管，能过就是好的 /oh。

最开始又双叒叕看错题了，浪费了十多分钟 /ll。

这个东西显然具有单调性啊，考虑二分，二分答案。

check 怎么写呢？考虑这样的贪心策略：

  1. 先找出右端点最靠左的线段作为当前线段，并记录 cnt 表示当前的总线段数，初始 cnt=1；
  2. 以当前线段的右端点 mid 为下一线段的左端点限制（下一线段的左端点不得小于此值），并在合法的所有下一线段中取右端点最靠左的；
  3. 如果不存在合法的下一线段，则 break 整个循环并跳至第 6 步；
  4. 让 cnt \gets cnt+1 并让下一线段作为当前线段；
  5. 回到步骤 2 循环这个过程；
  6. 检查是否 cnt \ge k，如果 cnt \ge k 则 check 通过，否则失败。

这个策略显然是没问题的，但是如何维护这些情况呢？

因为在找下一线段时，左端点有大小限制，且限制的是一个长度后缀，所以可以按左端点对所有线段升序排序。

但是在左端点有限制的同时，又需要找到右端点最靠左（即最小）的，这个怎么办？好做，我们再对排序后的线段，统计后缀最小右端点并记录下其线段编号即可。

时间复杂度 O(n \log V \log n)，其中 \log V 是因为二分答案，\log n 是因为 check 函数中的二分查找。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 2e5+5;
struct node{int x,y;}a[N];
int n,k,l=1,r,Ans=-1,mnid[N];
int read(){
    int su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
bool cmp(node d1,node d2){
    return (d1.x<d2.x);
}
int Find(int num,int l,int r){
    int res=0;
    while(l<=r){
        int mid=(l+r)>>1;
        if(a[mid].x>=num)res=mid,r=mid-1;
        else l=mid+1;
    }return res;
}
bool check(int ko){
    int cnt=1,now=mnid[1],lsty=a[now].y;
    while(1){
        int ll=Find(lsty+ko,now+1,n);
        if(!ll)break;
        int nxt=mnid[ll];
        now=nxt,lsty=a[now].y,cnt++;
    }return (cnt>=k);
}
int main(){
    n=read(),k=read();
    for(int i=1;i<=n;i++)
        a[i].x=read(),a[i].y=read(),r=max(r,a[i].y);
    sort(a+1,a+n+1,cmp);
    a[n+1].y=r+1,mnid[n+1]=n+1;
    for(int i=n;i>=1;i--)
        if(a[i].y<=a[mnid[i+1]].y)mnid[i]=i;
        else mnid[i]=mnid[i+1];
    while(l<=r){
        int mid=(l+r)>>1;
        if(check(mid))Ans=mid,l=mid+1;
        else r=mid-1;
    }cout<<Ans<<"\n";
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！