题目描述:

小明公司的办公区有一条长长的走廊，由 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。
试题 J: 扫地机器人 15第十届蓝桥杯大赛软件类省赛 Java 大学 C 组
【输出格式】
输出一个整数表示答案。
【样例输入】
10 3
5
2
10
【样例输出】
6

思路:

/***一起扫 平均分配
我的方案2:
采用分配法:
第一个机器人固定前面的
最后一个机器人固定后面的区域
中间的进行循环分配:分配规则:
用一个数组包括中间区域的数量field[2,4]
一个数组包括机器人的分配的区域robot[1,0,0]
每个区域只能分配给左右两个机器人,
每次分配一个,谁小就分配给谁,知道分配完毕,退出循环
robot[i]>robot[i+1] fielt[i]-- robot[i]++
*/

结果:找出max(robot) = 3 * 2 = 6

 public static int test3(int[] robot,int k){
        int[] field = new int[k-1];//2
        int[] robots = new int[k];//3
        int i1=0;
        while (true){
            if (robot[i1]==1){
                robots[0]=i1;
                break;
            }
            i1++;
        }

        int i2=robot.length-1;
        while (true){
            if (robot[i2]==1){
                robots[k-1] = robot.length - i2-1;
                break;
            }
            i2--;
        }
        System.out.println(Arrays.toString(robots));
        System.out.println("i1="+i1 +"i2="+i2);

        //开始搞field
        int j1=i1+1;
        for (int i = 0; i < field.length; i++) {//区域的个数
            for (; j1 < i2; j1++) {
                if (robot[j1]==1){
                    break;
                }
                field[i]++;
            }
            j1++;
        }

        System.out.println(Arrays.toString(field));

        //开始分配 filed分配给robots
        boolean flag = true;
        while (flag){
            flag = false;
            for (int j = 0; j <field.length ; j++) {
                if (field[j]>0){
                    flag = true;
                    if (robots[j]<=robots[j+1]){
                        robots[j]++;
                    }else {
                        robots[j+1]++;
                    }
                    field[j]--;
                }

            }
        }
        //分配完成后robot的情况
        System.out.println("每个机器人的分配数量="+Arrays.toString(robots));



        //找出最多打扫的机器人
        int max=0;
        for (int i = 0; i < robots.length; i++) {
            max = Math.max(robots[i],max);
        }
        return max*2;
    }

    public static void main(String[] args) {
        //test1();
        System.out.println(test3(new int[]{0, 1, 0, 0, 1, 0, 0, 0, 0, 1}, 3));
        System.out.println(test3(new int[]{1,0,1,0,0,0,0,0,0,0,1}, 3));
        System.out.println(test3(new int[]{1,0,0,0,1,0,0,0,0,0,1}, 3));
        System.out.println(test3(new int[]{1,1,1,1,1,0,0,0,0,0,1}, 6));
    }