Jumping Through Segments

题目描述

Polycarp is designing a level for a game. The level consists of n segments on the number line, where the i -th segment starts at the point with coordinate l_i and ends at the point with coordinate r_i .

The player starts the level at the point with coordinate 0 . In one move, they can move to any point that is within a distance of no more than k . After their i -th move, the player must land within the i -th segment, that is, at a coordinate x such that l_i \le x \le r_i . This means:

After the first move, they must be inside the first segment (from l_1 to r_1 );
After the second move, they must be inside the second segment (from l_2 to r_2 );
...
After the n -th move, they must be inside the n -th segment (from l_n to r_n ).

The level is considered completed if the player reaches the n -th segment, following the rules described above. After some thought, Polycarp realized that it is impossible to complete the level with some values of k .

Polycarp does not want the level to be too easy, so he asks you to determine the minimum integer k with which it is possible to complete the level.

输入格式

The first line contains a single integer t ( 1 \le t \le 10^4 )—the number of test cases. Descriptions of the test cases follow.

The first line of each test case contains a single integer n ( 1 \le n \le 2 \cdot 10^5 )—the number of segments in the level.

The following n lines.

The i -th line contain two integers l_i and r_i ( 0 \le l_i \le r_i \le 10^9 )—the boundaries of the i -th segment. Segments may intersect.

It is guaranteed that the sum of n over all test cases does not exceed 2 \cdot 10^5 .

输出格式

For each test case, output a single integer—the minimum value of k with which it is possible to complete the level.

样例 #1

样例输入 #1

样例输出 #1

提示

In the third example, the player can make the following moves:

Move from point 0 to point 5 ( 3 \le 5 \le 8 );
Move from point 5 to point 10 ( 10 \le 10 \le 18 );
Move from point 10 to point 7 ( 6 \le 7 \le 11 ).

Note that for the last move, the player could have chosen not to move and still complete the level.

二分思路

这题本身想到二分并不难，但是check函数并不好写，因为k只是每步的一个最大值，具体每步的最优解并不能确定。我最开始正向想了很久，都没办法解决每步具体走多远的问题，而且还牵扯到是正向走还是反向走。最后看了题解才明白。

这题既然正向思考不通过，那么可以反向思考，想每一步走后都会落在哪里，求出每步可能走到的范围，与下一步要求的范围求交集，为空则该方案不可行。

对于每步的范围，设 l , r 为目前可走到的左右边界,( lnxt, rnxt )为下一步的要求范围，则 ( l - k, r + k ) 即为下一步可走到的范围，则 ( l - k, r + k ) \cap ( lnxt, rnxt )即为下一步按题意能到达的范围

求并集

这里还有个小问题，并集怎么求。
其实只要找到两集合左端点的最大值，和右端点的最小值，最后用得到的新的左右端点的大小判断是否为空就行了。

l = max(l, li[i]);
r = min(r, ri[i]);
if (l > r) return false;

AC代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <iostream>

using namespace std;

const int MAX = 2e5 + 10;

int li[MAX];
int ri[MAX];//每步要求区域

bool check(int x, int n)
{
    int l = 0, r = x;//可到达区域 
    for (int i = 1; i <= n; i++)
    {
        l = max(l, li[i]);
        r = min(r, ri[i]);
        if (l > r) return false;
        l -= x;
        r += x;
    }
    return true;
}

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n = 0;
        scanf("%d", &n);//步数
        for (int i = 1; i <= n; i++) scanf("%d %d", &li[i], &ri[i]);

        int l = 0, r = 1e9, mid = 0;
        while (l < r)
        {
            mid = l + r >> 1;
            if (check(mid, n)) r = mid;
            else l = mid + 1;
        }//二分

        printf("%d\n", l);
    }
    return 0;
}

目录CONTENT

Jumping Through Segments【二分】