首页 > 试题广场 >

编程题2

[编程题]编程题2

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

算法知识视频讲解

牛客8046156号

#解析：https://blog.csdn.net/weixin_42001089/article/details/87114410
n,x = [int(e) for e in input().split()]
x = x-1
mintemp = 10**9
home = []
homemin = []
for i,e in enumerate(input().split()):
    e = int(e)
    home.append(e)
    if e<mintemp:
        homemin = []
        homemin.append(i)
        mintemp = e
    if e==mintemp:
        homemin.append(i)
i = 0
while i<len(homemin) and homemin[i]<=x:
    i+=1
start = homemin[i-1]
startcur = start
result = [e-mintemp for e in home]
result[start] = n*mintemp
while startcur!=x:
    startcur = (startcur+1)%n
    result[startcur]-=1
    result[start]+=1
for e in result:
    print(e,end=' ')

发表于 2019-02-16 11:37:07 回复(0)

霍七

#include <iostream>
using namespace std;
int main()
{
    int n, x; cin >> n >> x; x--;
    unsigned long long *data = new unsigned long long[n];
    unsigned long long minnum = -1, minindex;
    for (int i = 0; i < n; i++) {
        cin >> data[i];
        minindex = data[i] < minnum || (data[i] == minnum && i <= x) ? i : minindex;
        minnum = data[i] < minnum || (data[i] == minnum && i <= x) ? data[i] : minnum;
    }
    if (x < minindex) {
        for (int i = 0; i <= x; i++) {
            cout << data[i] - minnum - 1 << " ";
        }
        for (int i = x + 1; i < minindex; i++) {
            cout << data[i] - minnum << " ";
        }
        cout << n*(minnum + 1) - minindex + x;
        for (int i = minindex + 1; i < n; i++) {
            cout << " " << data[i] - minnum - 1;
        }
    }
    else if (x >= minindex) {
        for (int i = 0; i < minindex; i++) {
            cout << data[i] - minnum << " ";
        }
        cout << n*minnum + x - minindex;
        for (int i = minindex + 1; i <= x; i++) {
            cout << " " << data[i] - minnum - 1;
        }
        for (int i = x + 1; i < n; i++) {
            cout << " " << data[i] - minnum;
        }
    }
    delete[] data;
    return 0;
}

发表于 2017-12-26 20:37:34 回复(1)

牛客50140947号

if __name__ == "__main__":
    n, x = list(map(int, input().split()))
    a = list(map(int, input().split()))
    x -= 1
    r = min(a)
    for i in range(len(a)):
        a[i]-=r
    s = x
    while(a[s]!=0):
        a[s]-=1
        s-=1
    a[s] += r*n + x-s
    for i in range(len(a)):
        print(a[i],end=' ')

发表于 2022-03-13 09:40:02 回复(0)

pein531

重新分配后，i房间的人应该是最少的（设为min），由于i房间的人先全部出来了，因此这min人是后来循环分配的过程中再分配进来的，其他房间肯定至少比原来多了min人。

即i房间里在分配之前至少有n*min人。将分配之后的各房间人数减去这个值，然后从x房间往前倒推即可，遇到房间人数为0时，找到了i房间，停止倒推。

import java.lang.System;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] temp = br.readLine().trim().split(" ");
        int n = Integer.parseInt(temp[0]), x = Integer.parseInt(temp[1]);
        // 减1将编号转换为索引
        x --;
        String[] strArr = br.readLine().split(" ");
        long[] a = new long[n];
        for(int i = 0; i < n; i++) a[i] = Long.parseLong(strArr[i]);
        long min = a[0];
        // 人数最少的房间就是i房间（可能有多个最小值）
        for(int i = 1; i < n; i++)
            if(a[i] < min) min = a[i];
        // 先将最小值减去，肯定有一个元素会变成0
        for(int i = 0; i < n; i++) a[i] -= min;
        // 每个房间都至少增加了i房间的min人
        long count = min * n;        // 对i房间的原本人数进行初始化
        // 从x开始倒推
        while(a[x] != 0){
            // 把当前房间的人减1，因为他原本属于i房间
            a[x] --;
            // i房间人数加1
            count ++;
            // 房间号往前推
            x --;
            if(x < 0) x = n - 1;
        }
        // 找到第i个房间了，将属于它的count人放入其中
        a[x] = count;
        for(int i = 0; i < n; i++) System.out.print(a[i] + " ");
        System.out.println();
    }
}

发表于 2021-01-27 17:34:05 回复(0)

Python

maoxiaomao

这就超时就很离谱

n,x=map(int, input().strip().split())
A=list(map(int, input().strip().split()))
i=x-1
r=0
flag=0
while A[i]>0:
    A[i]-=1
    if A[i]==0 and flag==0:
        index=i
        flag=1
    r+=1
    i-=1
    if i<0:i=len(A)-1
A[index]=r
print(*A)

发表于 2021-05-26 10:56:10 回复(0)

Monkey_King_KK

#include <bits/stdc++.h>
using namespace std;
 
void solve(vector<long>& arr, int lastNum, long minValue)
{
    long leftNum = 0;
    int flag = lastNum;
    for (int i = 0; i < arr.size(); ++i)
    {
        arr[i] -= minValue - 1;
    }
    leftNum += (minValue-1) * arr.size();
    while (true)
    {
        if (arr[flag-1] == 0)
        {
            arr[flag-1] += leftNum;
            break;
        }
        arr[flag-1]--;
        leftNum++;
        if (flag-1 == 0)
        {
            flag = arr.size();
        }
        else
        {
            flag--;
        }
    }
    for (auto j: arr)
    {
        cout << j << " ";
    }
}
 
int main()
{
    int n, x;
    scanf("%d%d", &n, &x);
    vector<long> arr(n, 0);
    long minValue = 0x3f3f3f3f;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &arr[i]);
        if (arr[i] < minValue)
        {
            minValue = arr[i];
        }
    }
    solve(arr, x, minValue);
    return 0;
}

发表于 2020-08-15 14:56:54 回复(0)

-koil___

#include <bits/stdc++.h>
using namespace std;
int main() {
        long long n,x;
        cin>>n>>x;
        vector<long long> ans(n+1,0);
        for(int i=1;i<=n;i++)
                cin>>ans[i];

        long long min_=ans[1];
        for(int i=1;i<=n;i++)
                if(min_>ans[i])
                        min_=ans[i];

        int index=x;
        while(ans[index]!=min_)
        {
                index--;
                if(index<1)
                        index=n;
        }
        for(int i=1;i<=n;i++)
                ans[i]-=min_;
        ans[index]=n*min_;
        while(x!=index)
        {
                ans[x]--;
                ans[index]++;
                x--;
                if(x<1)
                        x=n;
        }
        for(int i=1;i<=n;i++)
                cout<<ans[i]<<" ";
        cout<<endl;
    return 0;
}

发表于 2019-08-22 01:44:57 回复(0)

牛客1659416

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

int main()
{
    int n,x;
    while(cin>>n>>x)
    {
        long long h[n];
        for (int i=0; i<n; i++)
            cin>>h[i];
        vector<int> v;
        int mi=0;
        v.push_back(mi);
        for (int i=1; i<=n-1; i++)
        {
            if (h[i]<h[mi])
            {
                mi=i;
                v.clear();
                v.push_back(mi);
            }
            else if (h[i]==h[mi])
            {
                mi=i;
                v.push_back(mi);
            }
        }
        int pos;
        if (v.size()==1)
            pos=v[0];
        else
        {
            if (x-1<v[0] || x-1>v[v.size()-1])
                pos=v[v.size()-1];
            else
            {
                if (count(v.begin(),v.end(),x-1)==1)
                    pos=x-1;
                else
                {
                    for (int i=0; i<v.size()-1; i++)
                    {
                        if (v[i]<x-1 && x-1<v[i+1])
                        {
                            pos=v[i];
                            break;
                        }
                    }
                }
            }
        }
        for (int i=0; i<n-1; i++)
        {
            if (pos<x-1)
            {
                if (i>pos && i<=x-1)
                    cout << h[i]-h[pos]-1 << ' ';
                else
                {
                    if (i!=pos)
                        cout << h[i]-h[pos] << ' ';
                    else
                        cout << n*h[pos]+x-1-pos << ' ';
                }
            }
            else if (pos>x-1)
            {
                if (i>x-1 && i<pos)
                    cout << h[i]-h[pos] << ' ';
                else if (i>x-1 && i==pos)
                    cout << n*h[pos]+n-(pos-(x-1)) << ' ';
                else
                    cout << h[i]-h[pos]-1 << ' ';
            }
            else
            {
                if (i!=pos)
                    cout << h[i]-h[pos] << ' ';
                else
                    cout << n*h[pos] << ' ';
            }
        }
        if (pos<x-1)
        {
            if (x-1==n-1)
                cout << h[n-1]-h[pos]-1 <<endl;
            else
                cout << h[n-1]-h[pos] << endl;
        }
        else if (pos>x-1)
        {
            if (pos==n-1)
                cout << n*h[pos]+n-(pos-(x-1)) << endl;
            else
                cout << h[n-1]-h[pos]-1 << endl;
        }
        else
        {
            if (pos<n-1)
                cout << h[n-1]-h[pos] << endl;
            else
                cout << n*h[pos] << endl;
        }
    }
    return 0;
}

发表于 2018-03-28 10:02:17 回复(0)

泣血残阳

#include <iostream>
#include <vector>
#include <cstdio>
#include <string>

using namespace std;

void print(vector<long long>& nums) {
    int n = nums.size();
    for(int i = 0; i < n; i++) {
        printf("%lld", nums[i]);
        if(i != n - 1)
            printf(" ");
        else
            printf("\n");
    }
}

int main() {
    int n, x;
    scanf("%d%d", &n, &x);
    vector<long long> nums(n, 0);
    for(int i = 0; i < n; i++) {
        scanf("%lld", &nums[i]);
    }
    vector<int> index;
    for(int i = 0; i < n; i++) {
        if(index.empty())
            index.push_back(i);
        else {
            if(nums[i] < nums[index.back()])
                index = {i};
            else if(nums[i] == nums[index.back()])
                index.push_back(i);
        }
    }
    x = x - 1;
    int i = 0;
    while(i < index.size() && index[i] <= x)
        i += 1;
    int start = index[(i - 1 + index.size()) % index.size()];
    long long k = nums[start];
    for(int j = 0; j < n; j++)
        nums[j] -= k;
    nums[start] = n * k;
    int pos = start;
    if(pos != x) {
        do {
            pos = (pos + 1) % n;
            nums[pos] -= 1;
            nums[start] += 1;
        } while(pos != x);
    } 
    print(nums);
    return 0;
}

该问题的关键在于定位开始被选出的位置，显然经过题意操作后，该位置的值将变为0，设该位置为i，则依次对i+1, i + 2, ... n - 1, 0, 1...i -1, i...各加1，若位置i被加了k次，则最后一轮的i + 1, i + 2... end的各个位置各加了k+1次，其他位置都加了k次。由此可以知道初始位置一定是变换后各个位置中值最小的。然后由上述规则可以知道，这个初始位置一定是在end之前的最后一个最小值（有时候最终序列中可能会有多个最小值）。

以上代码先求出所有最小值的位置，使用index数组从小到大记录。然后求出start位置，然后进行逆向过程，先对所有位置均减去k，将nums[start]置为n * k(表示执行了k轮分配)。然后计算最后一轮，若start位置不是end位置，依次将start + 1, start + 2, ..., end各个位置减1，并且将start位置的值每次相应+1.

显然该算法的复杂度为O(n)，与数据的数值大小无关。如果采用朴素方法，从end位置依次减1，直到遇到某个位置为0，则复杂度与数据的大小有关，无法解决数据很大的情况。

发表于 2018-02-20 13:25:31 回复(1)