蓝桥杯官网 试题 PREV-109 历届真题 扫地机器人【第十届】【省赛】【研究生组】【C++】【Java】【Python】三种解法

#include<bits/stdc++.h>
using namespace std;
const int maxx=1e5+10;

int n,k,a[maxx];

bool check(int x)
{
	int R=0;
	for(int i=0;i<k;i++)
	{
		if(a[i]-x>R)
		return false;
		else
		{
			if(a[i]<=R)
			R=a[i]+x-1;
			else
			R+=x;
		}
	}
	return R>=n;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n>>k;
	for(int i=0;i<k;i++)
	cin>>a[i];
	
	sort(a,a+k);
	int L=0,R=n;
	while(L<R)
	{
		int mid=(L+R)>>1;
		if(check(mid))
		R=mid;
		else
		L=mid+1;
	} 
	cout<< (L-1)*2 <<endl;
	return 0;
}

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)) {
			bj=mid;
			end=mid-1;
		}
		else {
			beg=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)
					t=aa[i]+x-1;
				else
					t+=x;
			}
			else
				return false;
		}
		return t>=n;
	}
}

def judge(m,q):
   for i in range(k):
       if (a[i]-q) <= m:
           if a[i]<= m:
               m = a[i] + q -1
           else:
               m = a[i] + q -(a[i] - m)
       else:
           return 0
   if m < n:
       return 0
   return 1
n,k = map(int,input().split())
a=[0]*k
for i in range(k):
   a[i]=int(input())
a.sort()
if (n/k) >=a[0]:
   q = int(n/k)
else:
   q = a[0]
 
for i in range(q,n+1):
   m = 0
   if judge(m,i)==1:
       print(2 * (i - 1))
       break