我要招人

去企业版

首页 > 试题广场 >

编程题2

[编程题]编程题2

热度指数：416 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

有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

输出

4 4 4

算法知识视频讲解

ohJune

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    vector<long long> a(n,0);
    for(int i = 0; i < n; i++) scanf("%lld",&a[i]);

    long long min = a[0], minIndex = 0;

    for(int i = 1; i < n; i++) {
        if(min > a[i]) {
            min = a[i];
            minIndex = i;
        } else if(min == a[i] && i <= x-1) {
            min = a[i];
            minIndex = i;
        }
    }
    for(long long &i: a) i -= min;
    
    x--;
    if(minIndex == x) {
        a[minIndex] += n*min;
    } else if(minIndex < x) {
        for(int i = minIndex + 1; i <= x; i++) a[i]--;
        a[minIndex] += (n*min + x - minIndex);
    } else if(minIndex > x) {
        for(int i = minIndex + 1; i < n; i++) a[i]--;
        for(int i = 0; i <= x; i++) a[i]--;
        a[minIndex] += (n*min + x + n - minIndex);
    }
    
    //for(long long i : a) cout << i << " ";
    for(int i = 0; i < n; i++) printf("%lld ",a[i]);
    return 0;
}

18/20 组用例通过，还有两组不知道问题在哪里...

发表于 2023-03-09 17:24:09 回复(1)

xingwy

#include <iostream>

#include <vector>

using namespace std;

int main(){

long long n, k, min = 1000000000;

cin>>n>>k;

vector<long long> vec;

for(int i=0; i<n; i++){

long long tmp;

cin>>tmp;

if(min > tmp){

min = tmp;

}

vec.push_back(tmp);

}

for(inti=0; i<n; i++){

vec[i] -= min;

}

min = min * n;

while(true){

if(vec[(k-1+ n)% n] == 0){

vec[(k-1+ n)% n] = min;

break;

}else{

vec[(k-1+ n)% n]--;

k--;

min++;

}

for(inti=0; i < n; i++){

cout<<vec[i]<<" ";

}

return0;

}

编辑于 2019-03-15 22:48:48 回复(0)

7志

   #include<iostream>  
   #include<vector>  
   using namespace std;  
   intmain(void){  
       intn,x;  
       cin>>n;  
       cin>>x;  
       vector<int> a(n,0);//创建数组等待接受输入数据  
       for(int i=0;i<n;i++)  
           cin>>a[i];  
       int i=x-1,count=0;//初始化开始运算位置以及计数清零  
       while(a[i]){//判断回溯的数值是否为0 如果是0则可以代表这就是i房间
  
           count++;//计算i房间的人被分到多少个房子,也就代表i房间本来有多少个人  
           a[i]-=1;//回溯的时候每个i+房间都需要减掉被增加的人  
           i=i==0?n-1:i-1;//判断是否回到第一个房间,如果回到第一个就重新从最后位置开始回溯  
       }  
       a[i]=count;//恢复原始分布  
       for(int i=0;i<n;i++){  
           cout<<a[i]<<' ';  
       }  
   }  
   //此函数运行通过80%的Case另外20%是运行超时,如果你有好的想法,欢迎赐教~
  

发表于 2018-08-11 19:57:10 回复(0)

Leo8888

public class Main {

    public static void getRoomNumbers(int[] arrays,int totals,int last){
        int min = arrays[0];
        int pos=0;
        int count=0;
        for(int i=1;i<totals;i++){
            if(arrays[i]<min){
                min = arrays[i];
                pos =i;
            }
        }
        if(min==0){
            //分配未到一圈
            if(last>pos){
                //最后分配房间号在被拆分房间之后
                for(int i=pos+1;i<last;i++){
                    arrays[i]-=1;
                    count++;
                }
            }else{
                //最后分配房间号在被拆分房间之前
                for(int i=pos+1;i<totals;i++){
                    arrays[i]-=1;
                    count++;
                }
                for(int i=0;i<last+1;i++){
                    arrays[i]-=1;
                    count++;
                }

            }
            arrays[pos]=count;
        }else{
            //分配大于等于一圈
            for(int i=0;i<totals;i++){
                arrays[i]-=min;
                count++;
            }
            if(last>pos){
                //最后分配房间号在被拆分房间之后
                for(int i=pos+1;i<=last;i++){
                    arrays[i]-=1;
                    count++;
                }
            }else{
                //最后分配房间号在被拆分房间之前
                for(int i=pos+1;i<totals;i++){
                    arrays[i]-=1;
                    count++;
                }
                for(int i=0;i<last+1;i++){
                    arrays[i]-=1;
                    count++;
                }
            }
            arrays[pos]=count;
        }


        for(int e:arrays){
            System.out.print(e+" ");
        }
    }

    public static void main(String[] args) {
        // 4 4 4
        int[] arrays = {6,5,1};
        int totals = 3;
        int last = 1;
        getRoomNumbers(arrays,totals,last-1);

    }

}

发表于 2018-05-11 23:53:54 回复(1)