CF1907D

zibenlun · 2023-12-11 20:53:21 · 题解

Solution

为什么没有人写题解呢？

题目链接

挺简单的一题，题目大体意思就是求最少跳多远就能从第一条线段走到最后一条线段。

很容易想到二分，所以重点在于怎么判断当前长度是否合法，可以想到维护从一开始到现在所能跳到的范围。

时间复杂度 O(nlogn)

CODE

#include<bits/stdc++.h>
using namespace std;
//从来不用的快读快写 
inline long long read() {
    long long s=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') {
        s=(s<<3)+(s<<1)+(ch^48);
        ch=getchar();
    }
    return s;
}
inline void write(long long x) {
    if(x<0) putchar('-'),x=-x;
    if(x>9) write(x/10);
    putchar(x%10+'0');
}
int t,n;
struct nd{
    long long l,r;
}a[1000005];//存一下左右边界 
bool check(int k){
    long long l=0,r=0;
    for(int i=1;i<=n;i++){
        if(a[i].l>r){
            if(a[i].l-r>k) return false;
            r=min(a[i].r,r+k);
            l=a[i].l;
        }
        else if(a[i].r<l){
            if(l-a[i].r>k) return false;
            l=max(l-k,a[i].l);
            r=a[i].r;
        }
        else {
            r=min(a[i].r,r+k);
            l=max(a[i].l,l-k);
        }
    }
    return true;
}
int main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r;
        long long l=0,r=1e9+5,ans=0x3f3f3f3f3f3f;//二分长度 
        while(l<r){
            long long mid=(l+r)>>1;
            if(check(mid)){
                r=mid-1;
                ans=min(ans,mid);//记录答案 
            }
            else {
                l=mid+1;
            }
        }
        for(int i=max(ans-10,1ll*0);i<=ans;i++){
            if(check(i)) {
                ans=i;
                break;
            }
        }
        //本人的二分老是挂，所以写了个补丁…… 
        cout<<ans<<"\n";
    } 
    return 0;
}