编程题2

[编程题]编程题2

热度指数：191 时间限制：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

算法知识视频讲解

C/C++

布白

从房间 x 出发往前（注意头尾成环）寻找第一个最小人数的房间，即为被重新分配的房间 iii；

然后该房间人数代表的循环分配的轮数 cycle，要注意从房间 (iii + 1) 往后到房间 x（注意头尾成环）这一部分是多了一轮循环的；

找到了分配房间 iii 和循环分配轮数 cycle，就可以把房间人数恢复回去了，代码如下：

int main()
{
    int n, x;
    cin >> n >> x;
    long room[n];
    for (int i = 0; i < n; i++) cin >> room[i];

    x--;
    int iii = x;
    long min = room[x];
    for (int i = x + n; i > x; i--)   // 寻找分配房间 iii
        if (room[i % n] < min) min = room[i % n], iii = i % n;

    if (iii > x) x += n;
    for (int i = iii + 1; i <= x; i++) room[i % n]--;   // 处理多一轮循环
    long cycle = room[iii];
    for (int i = 0; i < n; i++) room[i] -= cycle;   // 处理所有房间
    room[iii] = cycle * n + x - iii;   // 恢复分配房间人数

    for (int i = 0; i < n - 1; i++) cout << room[i] << " ";
    cout << room[n - 1];

    return 0;
}

编辑于 2018-03-24 15:08:05 回复(0)

神秘牛客人

python AC

import sys
num, index = list(map(int, sys.stdin.readline().strip().split()))
index-=1
room = list(map(int, sys.stdin.readline().strip().split()))
min_value = min(room)
i_num = min_value * num
min_index_s = []
min_index = -1
for i in range(num):
    if room[i] == min_value:
        min_index_s.append(i)
for k in range(len(min_index_s)):
    if index == min_index_s[k]:
        min_index = min_index_s[k]
        break
    elif index > min_index_s[k]:
        if k+1 == len(min_index_s):
            min_index = min_index_s[k]
            break
        else:
            if min_index_s[k+1] <= index:
                continue
            else:
                min_index = min_index_s[k]
                break
    else:
        if k == len(min_index_s)-1 and min_index_s[0] > index:
            min_index = min_index_s[k]
            break
extra = 0
if index >= min_index:
    extra = index - min_index
    for j in range(num):
        if j == min_index:
            print(i_num + extra, end=" ")
        elif j < min_index&nbs***bsp;j > index:
            print(room[j] - min_value, end=" ")
        elif j > min_index and j <= index:
            print(room[j] - min_value - 1, end=" ")
else:
    extra = num-1 - min_index + index + 1
    for j in range(num):
        if j == min_index:
            print(i_num + extra, end=" ")
        if j <= index&nbs***bsp;j > min_index:
            print(room[j] - min_value - 1, end=" ")
        elif j > index and j < min_index:
            print(room[j] - min_value, end=" ")

发表于 2022-04-27 22:05:23 回复(0)

Reyzal

//编程题2
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, x;
    while (cin >> n) {
        cin >> x;
        if (n == 0) continue;
        vector<long long> data(n);
        long long mindata = 0x7fffffff;
        for (size_t i = 0; i < n; i++) {
            cin >> data[i];
            mindata = min(data[i], mindata);
        }
        if (mindata == data[x - 1]) {
            for (auto& it : data) {
                it -= mindata;
            }
            data[x - 1] = mindata * n;
        } else {
            //从x往前出发，遇到的第一个最小值就是开始点
            int begin = x - 1 + n;
            int count = 0;
            while (mindata != data[begin % n]) {
                data[begin % n]--;
                count++;
                begin--;
            }
            for (auto& it : data) {
                it -= mindata;
            }
            data[begin % n] = mindata * n + count;
        }
        for (size_t i = 0; i < n; i++)
        {
            cout << data[i] << (i == n - 1 ? '\n' : ' ');
        }
    }

    return 0;
}

更多牛客网题解代码从https://github.com/ReyzalX/nowcoder获取

发表于 2018-03-23 21:55:53 回复(0)