题目描述

有n个房间，现在i号房间里的人需要被重新分配，分配的规则是这样的：

先让i号房间里的人全都出来，接下来按照 i+1, i+2, i+3, ...

的顺序依此往这些房间里放一个人，n号房间的的下一个房间是1号房间，直到所有的人都被重新分配。

现在告诉你分配完后每个房间的人数以及最后一个人被分配的房间号x，

你需要求出分配前每个房间的人数。数据保证一定有解，若有多解输出任意一个解。

输入描述

第一行两个整数n, x (2<=n<=10^5, 1<=x<=n)，代表房间房间数量以及最后一个人被分配的房间号；
第二行n个整数 a_i(0<=a_i<=10^9) ，代表每个房间分配后的人数。

输出描述

输出n个整数，代表每个房间分配前的人数。

输入例子1:

3 1
6 5 1

输出例子1：

4 4 4

解题思路

1. 暴力回溯：从最后一个房间往前逐个回溯减少1，直到某个房间人数减少为0，这个过程减少的总人数就是i号房间的人数，其他房间也变为起始人数。必须超时！！！！
2. 方法2，思路自己也想到了（但是还是参考了https://blog.csdn.net/yuanxu716/article/details/78290274）：
   • 如下图中所示：
   • 首先我们假设这个数组中人数最少的房间就是起始房间分配后的结果，因为每一次分配给其他房间1之后它自己才能获得1，如果有多个最小的那么久以终止房间x递减到第一个对应的最小值为准
   • 上述对应图中标红部分，我们可以顺着推，从起始房间开始分配，最后剩余min_val那么也就是说每个房间都至少加了min_val个数（因为分配时是从下一个开始的）。最后终止于房间x也即是说从起始房间向右转一圈到x又增加了1，即是图中标红的部分增加了min_val+1，蓝色部分则是表明只增加了min_val，最后一圈并没有转完。
   • 此时我们再看起始节点，根据计算的话应该是上述增加的和，合并起来其实就是=min_valn+d，因为每个都分配了min_val个，红色部分长度为d，每个多加1，所以增加1d的数量即可。
   • 参考是用c语言实现的，大致上没区别，但是要注意在Java中关于声明数组时为long类型，int类型默认最大值是2^31-1，当10个房间，每个房间都是10000000的时候最后起始房间会溢出报错，无法A成功。
   • 转载请注明出处，自绘

Java代码实现

package com.zhou.test1;
import java.util.*;
/**
 * Created by 强 on 2019/3/18.
 */
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt();
        long[] person_now = new long[n];
        long min_value = Integer.MAX_VALUE;
        for(int i=0; i<n; i++) {
            person_now[i] = sc.nextInt();
            min_value = Math.min(min_value, person_now[i]);
        }
        int index = x-1;
        int count = 0;
        while(person_now[(index+n)%n]!=min_value) {
            person_now[(index+n)%n] -= min_value+1;
            index--;
            count++;
        }
        person_now[(index+n)%n] = min_value*n + count;
        index--;
        while((index+n)%n!=x-1) {
            person_now[(index+n)%n] -= min_value;
            index--;
        }
        for(int i=0; i<n; i++) {
            System.out.print(person_now[i]+ " ");
        }
    }
}