1. if(robot[i]-len<=sweep)这个代码的意思是——如果机器人向左移动len个长度后,比现在sweep的位置(现在已经覆盖的范围)还要靠左,就是覆盖连续不起来,呢么这个len就是有问题的,退出函数,再继续循环。
2. 显然当每个机器人清扫的范围相同时,所用时间最小,所以这时候可以想到用二分算法,check条件(判断条件)是每个清扫范围都能被扫到。
输入:
10 3
5
2
10
输出:6
输出机器人清扫玩完所有区域至少花费的时间.
#include<bits/stdc++.h> using namespace std; int robot[100010]; int n,k; bool check(int len){ int sweep=0; int i; for(i=1;i<=k;i++){ if(robot[i]-len<=sweep){ if(robot[i]<=sweep){ sweep=robot[i]+len-1; } else{ sweep=sweep+len; } } else{ return 0; } } return sweep>=n; } int main() { scanf("%d",&n); scanf("%d",&k); int i; for(i=1;i<=k;i++){ scanf("%d",&robot[i]); } sort(robot+1,robot+k+1); int m,l=0,r=n,ans; while(l<=r){ m=(r+l)/2; if(check(m)){ r=m-1; ans=m; } else{ l=m+1; } } printf("%d",(ans-1)*2); return 0; }
3.if(robot[i]<=sweep)
这个代码的意思是robot[i]此时所处的位置在已经被上一个机器人清扫过的位置了,所以此时sweep的值为robot[i]向右走的len然后减去1(减去robot起始位置)
否则的话robot[i]此时所处的位置为上一个机器人还未清扫过的位置,此时这个机器人会优先往左清扫,即sweep=sweep+len;
4.sort(robot+1,robot+k+1);
sort函数的两个参数是排序的起点和终点位置,robot加1的原因是数组是从1开始排列的,而不是从0开始排列的。
5.if(check(m)){
r=m-1}是因为如果此时的m满足清扫的条件,呢么接下来应该找比m更小的范围(对应更小的时间)即往m的左区间更小的数去找。即r=m-1。
注:代码来自lanqiao6628158049