字节--房间分配

@[toc]

一、问题描述

有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

二、分析

•  来解释一下，题目里面的i是某一个房间i，我们不知道是那个具体的房间i，并不是所有房间都要重新分配，只是i房间重新分配.

初始情况：

4 4 4

现在第3房间的人重新分配

(为了与语言一致,即使得房间编号从0开始,代码中会认为是2号房间

4 4 0

1 1 1

1

最终结果为

6 5 1

•  题目本身不涉及什么算法，纯模拟。
•  第一种想法是，从最后一个分配房间逆推，每个房间减一个人，直到遇到某个房间人数减为0。
•  这个过程所减的总人数就是i号房间的人数，其它房间也变为起始人数。按照这个想法编码，case率80%，超时。
•  第二种想法是找到分配房间i的位置，再根据i房间当中的人数来还愿所有房间的人数
•  如下图中所示：
  
•  首先我们假设这个数组中人数最少的房间就是起始房间分配后的结果（就是问题当中的i房间）。因为每一次分配给其他所有房间1个人之后才给它自己分配1个人，所以最少人数的房间才有可能是i号房间。
•  如果发现有多个相同的最小值，那么就以终止房间x递减到第一个对应的最小值为准。

因为如果出现2个或者2个以上的最小值相等的情况，那么就说明i房间当中的人数无法分配一圈，一旦i房间中的人数可以分配一圈，那么i房间的人数增加1，其他所有房间都增加1，不可能出现相等的情况，所以如果出现多个相同的最小值的时候以终止房间x递减到第一个对应的最小值为准

•  上述对应图中标红部分，我们可以顺着推，从起始房间i开始分配，最后i的值为min_val，那么也就是说每个房间都至少加了min_val个数（因为分配时是从下一个开始的，i房间的人数都分配到min_val个，那么其他房间肯定至少有min_val个）。
•  最后终止于房间x也即是说从起始房间向右转一圈到x又增加了1，即是图中标红的部分增加了min_val+1，蓝色部分则是表明只增加了min_val，相当于最后一圈并没有转完，只转到x位置就停止了。
•  此时我们再看起始节点，根据计算的话应该是上述增加的和，合并起来其实就是=min_valn+d，因为每个都分配了min_val个，红色部分长度为d，每个多加1，所以增加1d的数量即可。

三、代码

#include <bits/stdc++.h>    
using namespace std; 
   
int main()    
{                                                                                                                                           
    int n ;    
    int x ;    
    cin>>n>>x; 
       
    //数组，存放每个房间分配完成后的人数
    long* person_now = new long[n];

	//保存数组中最少的人数，用来确定那个房间的人数被分配出去，即题目中的i房间    
    long min_value = INT_MAX;      
    for(int i = 0; i < n; i++)    
    {    
        cin>>person_now[i];    
        min_value = min(min_value, person_now[i]);    
    }    
         
    //题目中的房间号是从1开始的，所以-1
    int index = x - 1;   

	//用来保存没有转完一圈剩下的房间数，即x到i房间的距离，图中的d
    int count = 0;                 

	//开始，(index + n) % n的原因是index是不断减小的，因为在分配i房间人数时是以
	//i,i + 1,....,n,1,2,...i这种顺序的，所以我们是反着来还原的，即
	//index,index - 1,....1,0,n,n - 1,....index,所以是为了防止越界访问

	//!= min_value目的有两个：
	//1.因为我们是以index递减的顺序遍历的，那么第一个和min_val值相等的房间
	//刚好就是题目中的i号房间，也就是把人数拿出来分配的房间，避免了相同的min_val
	//情况；
	//2.从index递减到第一个等于min_val房间之间的所有房间一定是至少分配了
	//min_val + 1个人，也就是图中的红色部分，+ 1就是红色部分比蓝色部分
	//多走的半圈
    while(person_now[(index + n) % n] != min_value) 
    {    
    	//还原红色部分的原始房间
        person_now[(index + n) % n] -= min_value + 1;    
        //递减index下标
        index--;    
        count++;    
    }    
    
    //还原第i号房间的原始人数，就是最少房间的人数
    person_now[(index + n) % n] = min_value * n + count;
    index--;
    
    //还原图中的蓝色部分的原始人数，就是只分配了min_val个人数，最后没走完
    //一圈剩下的房间数
    while((index + n) % n != x - 1) 
    {
        person_now[(index + n) % n] -= min_value;
        index--;
    }
    
    //打印结果
    for(int i = 0; i < n; i++) 
    {
        cout<<person_now[i]<<" ";
    }
    return 0;
}