ZJ6. 编程题2
描述
有n个房间，现在i号房间里的人需要被重新分配，分配的规则是这样的：先让i号房间里的人全都出来，接下来按照 i+1, i+2, i+3, ... 的顺序依此往这些房间里放一个人，n号房间的的下一个房间是1号房间，直到所有的人都被重新分配。
现在告诉你分配完后每个房间的人数以及最后一个人被分配的房间号x，你需要求出分配前每个房间的人数。数据保证一定有解，若有多解输出任意一个解。
输入描述
第一行两个整数n, x (2<=n<=10^5, 1<=x<=n)，代表房间房间数量以及最后一个人被分配的房间号；输出描述
输出n个整数，代表每个房间分配前的人数。示例1
输入:
3 1 6 5 1
输出:
4 4 4
C++ 解法, 执行用时: 18ms, 内存消耗: 2128KB, 提交时间: 2022-02-08
#include<bits/stdc++.h>
using namespace std;
long long a[100005];
int main(){
long long n,x,minn=(long long)1e9+7,minIndex = -1;
scanf("%lld %lld",&n,&x);
x--;
for(int i=0;i<n;i++){
scanf("%lld",&a[i]);
if(minn>a[i]){
minIndex=i;
minn=a[i];
}
else if(minn==a[i]){
if(i<=x)
minIndex=i;
}
}
if(minIndex>x){
for(int i=n-1;i>=0;i--)
if(a[i]==minn){
minIndex=i;
break;
}
}
for(int i=0;i<n;i++)
a[i]-=minn;
a[minIndex]+=minn*n;
if(x!=minIndex){
if(minIndex>x)for(int i=minIndex+1;i<=x+n;i++){
a[i%n]--;
a[minIndex]++;
}
else for(int i=minIndex+1;i<=x;i++){
a[i%n]--;
a[minIndex]++;
}
}
for(int i=0;i<n;i++){
printf("%lld ",a[i]);
}
printf("\n");
return 0;
}
C++ 解法, 执行用时: 18ms, 内存消耗: 2168KB, 提交时间: 2021-04-11
#include <bits/stdc++.h>
// #include <algorithm>
using namespace std;
#define MAXN 200005
#define INF INT_MAX
#define MOD 1000000007
#define _for(i,a,b) for(int i=(a); i<(b); ++i)
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
long n, x;
long k=LONG_MAX;
cin>>n>>x;
x-=1;
long a[n];
long i=0;
for (long l = 0; l < n; ++l){
cin>>a[l];
if (a[l] <= k){
k = a[l];
}
}
i = x;
while(a[i] != k){i = (i + n -1)%n;}
// int min_idx;
// i = min_element(a, a+n) - a;
// long k = a[i];
long s=0;
// for (long j = (i+1)%n; j != x + 1; j=(j+1+n)%n ){
for(long j = x;j!=i;j=(j+n-1)%n)
{
a[j] --;
s++;
}
for (long j = 0; j < n; ++j){
a[j] -= k;
}
a[i] = n * k + s ;
// if (x > i){
// a[i] = n * k + x - i + k;
// }
// else{
// a[i] = n * k + x + n - i + k;
// }
for(long i=0; i<n; ++i){cout<<a[i]<<" ";}
return 0;
}
C++ 解法, 执行用时: 19ms, 内存消耗: 1656KB, 提交时间: 2021-03-28
#include <stdio.h>
int a[100010];
int read()
{
int sum=0;
char c=getchar();
while(c>'9' || c<'0') c=getchar();
while(c>='0' && c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int main(void)
{
int n,x;
scanf("%d%d",&n,&x);
for(int i=1;i<=n;i++) a[i]=read();
int min=2e9,pos;
for(int i=x;;)
{
if(a[i]<min) min=a[i],pos=i;
if(!(--i)) i=n;
if(i==x) break;
}
int temp=(x+n-pos)%n;
long long int r=a[pos];
for(int k=1;k<=n;k++)
{
if(k==pos) printf("%lld ",a[k]+(n-1)*r+temp);
else if((k+n-pos)%n<=temp) printf("%lld ",a[k]-r-1);
else if((k+n-pos)%n>temp) printf("%lld ",a[k]-r);
}
}
C 解法, 执行用时: 19ms, 内存消耗: 1656KB, 提交时间: 2021-02-25
#include <stdio.h>
int a[100010];
int read()
{
int sum=0;
char c=getchar();
while(c>'9' || c<'0') c=getchar();
while(c>='0' && c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
int main(void)
{
int n,x;
scanf("%d%d",&n,&x);
for(int i=1;i<=n;i++) a[i]=read();
int min=2e9,pos;
for(int i=x;;)
{
if(a[i]<min) min=a[i],pos=i;
if(!(--i)) i=n;
if(i==x) break;
}
int temp=(x+n-pos)%n;
long long int r=a[pos];
for(int k=1;k<=n;k++)
{
if(k==pos) printf("%lld ",a[k]+(n-1)*r+temp);
else if((k+n-pos)%n<=temp) printf("%lld ",a[k]-r-1);
else if((k+n-pos)%n>temp) printf("%lld ",a[k]-r);
}
}
C++ 解法, 执行用时: 20ms, 内存消耗: 2160KB, 提交时间: 2021-09-12
#include<stdio.h>
#include<limits.h>
#include<algorithm>
using namespace std;
#define ll long long
int n,x;
ll room[1500005];
int main(void){
scanf("%d%d",&n,&x);
ll mn=INT_MAX;
for(int i=0;i<n;i++){
scanf("%lld",&room[i]);
mn=min(mn, room[i]);
}
x-=1;
int pos=x;
while(room[pos]!=mn)
pos=pos>0?pos-1:n-1;
for(int i=0;i<n;i++)
room[i]-=mn;
int count=0;
for(int i=x;i!=pos;i=i>0?i-1:n-1){
room[i]-=1;
count+=1;
}
room[pos]+=count+n*mn;
for(int i=0;i<n;i++)
printf("%lld ",room[i]);
return 0;
}