题目描述

在 N 个方格的一维走廊上，放置 K 个扫地机器人，扫地机器人可以向左右方向移动，并将该方格清扫干净。每个机器扫完地后都需要回到初始位置，同时每个方格区域至少被清扫一次，每个机器人移动一格花费一节电池。

假设我们只需要花费所有机器人中消耗电池最多的那个机器人的电池数(其他机器人不管)。那么请输出我们需要购买电池数的最小值。

输入格式

多组测试数据，第一行是数据组数。
之后每组测试数据的第一行包含两个整数 N 和 K。接下来 K 行，每行一个整数 Ai。

输出格式

输出一个整数表示答案，每个答案占一行。

样例输入

1
10 3
5
2
10

样例输出

6

数据规模

1 ≤ T ≤ 20 (T为数据组数)
1 ≤ K < N ≤ 100000
1 ≤ Ai ≤ N

思路

一看到这种求最大xxx的最小值(k小值)，或者最小xxx的最大值(k大值),就要想到二分。
二分答案，然后check是否可以，check的方法就是先假设所有机器人都有着最多电池数，然后从小到大枚举每个机器人，然后先向左走，把左边界走到了后，再尽量向右走，若连左边界都走不到，那么就return false。

#include<bits/stdc++.h>
using namespace std;
const int N=100005;
int n,k,robot[N];
bool check(int x)
{
    int l=1;
    for(int i=0;i<k;i++)
    {
        int t=x-max(0,robot[i]-l);
        if(t<0) return false;
        l=robot[i]+t+1;
    }
    if(l<=n) return false;
    return true;
}
int main()
{
    cin>>n>>k;
    for(int i=0;i<k;i++) scanf("%d",&robot[i]);
    sort(robot,robot+k);
    int l=0,r=N-3;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<2*l<<endl;

    return 0;
}