题目 2310: 蓝桥杯2019年第十届省赛真题-扫地机器人

这是个难题，不是我说的
会思路了。
要求的是最小的机器人的扫描范围，没别的，就是从小到大枚举扫描范围，然后用一个check函数，check函数需要用到左端点如果符合就输出步数
1.扫描范围：设置为Q。扫描范围是自己能到的最大的长度。例如上面的第一个机器人的扫描范围是4，第二个是3，第三个是3.
2.左端点：假设左端点左边的所有点都能被机器扫描到，L初始为0，从左到右增长，直到到区间最右边n。
3.check函数：用来判断当前的扫描范围能否把所有的点都扫描到

如果当前的L+Q <= a[i]的话，说明当前的左边界+区间长度都够不着 a[i]所在的位置，说明Q太小了直接return false；

如果L+Q>a[i]说明能够到，然后进去再判断：a[i]可能在L左边也可能在a[i]右边

如果a[i]在L左边，说明a[i]不需要扫描a[i]左边，只扫描a[i]右边就够了。更新L=a[i]+Q - 1，//Q是总区间长度，包括a[i]本身，所以要减去a[i]这个点。
.
如果a[i]在L右边，说明a[i]既需要能够到L，还要尽可能向右够到最远，更新L = a[i] + Q - (a[i] - L )，即L + Q从L直接加Q，一个道理。

4.步数：这个其实是和扫描范围区间长度有关系的，扫描范围是包括a[i]点本身能到的最大的长度，三个点1，2，3，从1走到3需要2步，再走回来仍需2步，区间长度假设为Q，则步数z= 2*(Q-1)，相当于刨去a[i]点不走。
5.在check函数里，

#include
#include
#include
using namespace std;
const int N = 110000;
int a[N];
int n,k;
bool check(int L,int Q)
{
    for(int i=1;i<=k;i++)
    {
        if(a[i]<=Q+L) //L+Q >= a[i]说明左区间+扫描区间大于等于当前a[i]，能扫到a[i],或者说a[i]扫描范围能接上L
        {
            if(a[i]<=L) //a[i]<=L 说明a[i]点在扫描的范围左边，已经过去了，  
            {
                L=a[i] + Q -1; //Q是包含a[i]这个点本身的区间长度，
                //如果a[i]在左边界左边，那a[i]的扫描范围全部用来扫描右区间，不要忘记-1：Q-1=扫描总长度-a[i]点本身
            }
            else if(a[i] > L) //a[i]在左边界的右边
            {
                L=a[i] + Q -(a[i]-L);
            }
        }
        else return false;//a[i] > Q+L说明以现在的机器人a[i]扫描范围Q都接不上左边界L
    }
    if(L>n>>k;
    for(int i=1;i<=k;i++) cin>>a[i];
    int Q,L;// Q:每个机器人能扫到的区间大小。L：左边界，L左边的代表已经全部被扫过
    sort(a+1,a+1+k);
      Q=max(n/k,a[1]);
    for(Q;Q<=n;Q++)
    {
        L=0;
        //cout<