扫地机器人蓝桥杯

本题思路

本题核心二分，本题利用二分举出各个扫地机器人人的清扫范围，在数学里我们知道，在一个空间里均等的花费最优，也就是无论有多少个机器人，这些机器人清扫的范围尽量相同，这样花费最少也就是最优

所以本题利用二分，举出范围，然后验证这个范围是否可以满足，要求清扫完n个区域，模拟这个清扫的过程，如果根据这个范围，过程必须是无间断的（也就是上一个的清扫结尾，后面的那个机器人必须要能到达），而且最后到达的点，是可以到达n长度的，那么就是满足条件的，记录这个值，并缩小x的大小，直到退出，因为这些机器人是同时工作的，且最后必须要回到原位，那么我们就将范围乘2即可

下面上代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;public class Main扫地机器人 {//本题非常有意思，是一个典型的二分使用//简单来说就是本题使用二分来查找满足要求的机器人清扫范围//穷举出满足要求的范围，然后继续缩小，最后留下的就是最小范围，而因为要回到原位，就是x-1的两倍//其中检验符不符合要求，就是去模拟整个过程，最后长度可以达到n,就说明满足要求//不能到达说明x太小，能到可能满足或者太大，指针向后移//一个二分的妙用，让暴力又有了一个新方法，我认为很完美//但还是网上思路，依然需要继续加强自身static int aa[],n,m;public static void main(String[] args) throws IOException {StreamTokenizer x = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));x.nextToken();n=(int)x.nval;x.nextToken();m=(int)x.nval;aa=new int[m];for(int i=0;i<m;i++) {x.nextToken();aa[i]=(int)x.nval;}Arrays.sort(aa);int beg=0,end=n,mid,bj=0;while(beg<=end) {mid=(beg+end)>>1;if(check(mid)) {//足够减少xbj=mid;end=mid-1;}else {//不足增加xbeg=mid+1;}}out.println((bj-1)*2);out.flush();}public static boolean check(int x) {int t=0;for(int i=0;i<m;i++) {if(aa[i]-x<=t) {//如果可以到达上个机器人的清扫边界if(aa[i]<=t)//如果这个机器人的位置还要小于前个机器人的清扫边界,那么这个机器人的清扫边界,就是机器人位置加上清扫范围xt=aa[i]+x-1;else//如果本身大于它那么范围就是上次的清扫范围加上清扫的范围xt+=x;}else//范围不够return false;}return t>=n;//检查范围是否足够}
}

如有侵权，联系删