蓝桥杯—扫地机器人

试题 J: 扫地机器人
时间限制: 1.0s 内存限制: 512.0MB 本题总分：25 分
【问题描述】
小明公司的办公区有一条长长的走廊，由 N 个方格区域组成，如下图所
示。

走廊内部署了 K 台扫地机器人，其中第 i 台在第 Ai 个方格区域中。
已知扫地机器人每分钟可以移动到左右相邻的方格中，并将该区域清扫干
净。
请你编写一个程序，计算每台机器人的清扫路线，使得
1. 它们最终都返回出发方格，
2. 每个方格区域都至少被清扫一遍，
3. 从机器人开始行动到最后一台机器人归位花费的时间最少。
注意多台机器人可以同时清扫同一方块区域，它们不会互相影响。
输出最少花费的时间。
在上图所示的例子中，最少花费时间是 6。第一台路线：2-1-2-3-4-3-2，清
扫了 1、2、3、4 号区域。第二台路线 5-6-7-6-5，清扫了 5、6、7。第三台路线
10-9-8-9-10，清扫了 8、9 和 10。
【输入格式】
第一行包含两个整数 N 和 K。
接下来 K 行，每行一个整数 Ai。

【输入样例】

10 3

2

5

10

【输出样例】

6

【思路分析】

       这道题的目的就是让我们求出机器人从扫地到回归原位的最小时间花费所以我们首先要确定的就是每个机器人负责的格子数也就是边界，在确定了边界之后我们只需要找出机器人扫地的最大时间花费就是我们要求的解。也就是说我们需要不断的调整机器人扫地的边界来找出扫地的最大时间花费再从这些最大花费中找出机器人的最小花费就是机器人从开始行动到最后一台机器人归位的最少时间花费

【代码演示】

import java.util.Arrays;
import java.util.Scanner;

public class day_6_10 {
	//这道题主要的思路就是不断的调整机器人扫地的边界来找出
	//扫地的最大时间花费中的最小时间花费
	static int sum=Integer.MAX_VALUE;//所有最大花费中的最小花费
	static int n;//格子数
	static int k;//机器人数
	static int[] karr;//机器人位置
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();//n代表格子数
		k=sc.nextInt();//k代表机器人的数量
		karr=new int[k+1];
		//输入每个机器人的位置
		for (int i = 1; i < karr.length; i++) {
			karr[i]=sc.nextInt();
		}
		Arrays.sort(karr);
		
		System.out.println(f(1,0,0));
	}

	//index代表了第几个机器人
	//L代表了机器人的左边界
	//count代表了本次的最大时间花费
	public static int f(int index,int L,int count) {
		//确定最后一个机器人的时间花费
		if(index==k) {
			int aa=(n-L)*2-2;
			count=aa>count?aa:count;
			//找出扫地最大花费中的最小花费
			sum=sum>count?count:sum;
			return sum;
		}
		//通过循环加递归来不断的调整机器人的扫地边界
		for (int i = karr[index]; i <karr[index+1] ; i++) {
			//每个机器人的时间花费
			//公式：(right-left)*2-2右边界减去左边界*2再减去一个2
			//因为起始位置和最右边的区域只走了一次而其他的格子需要往返
			int aa=(i-L)*2-2;
			//判断本次调整的边界是否是花费时间最多的
			count=count>aa?count:aa;
			//确定下一个机器人的边界和时间花费
			f(index+1,i,count);
		}
		return sum;
	}
}