Meetinanotherworld,enjoytastyfood!

NC221651. Meetinanotherworld,enjoytastyfood!

描述

One evening, Mr.X passed by Luojia Gate as usual and found a long line of KFC at the gate. People waited in line the night before for a limited number of 50 pairs of Genshin badges to be handed out at 10 a.m. However, unfortunately, the number of people in the queue is well over 50. That means there will be people waiting in line all night but not getting the badge they are looking forward to. And the people themselves know it. So they are hoping that a few more people will leave the queue before their patience runs out.
Assuming there are $n$ person waiting in the queue, and the initial patience value of the $i^{th}$ person is $x_i$ . In each round, each person will lose the patience value equivalent to his/her current ranking in order from front to back successively for one time. With each additional round, everyone’s patience diminishes once. If a person's patience value is less than or equal to zero, he or she will immediately abandon the queue and leave the queue. Note that when someone leaves the queue, the rank of the person behind him immediately changes.
Mr.X wants to know the order in which everyone will leave if the queue goes on forever.

输入描述

The first line contains an integer , representing the number of people in the queue.
The second line contains  integers , representing the current patience value of the  preson.

输出描述

Output  integers in one line, denoting the order in which  people leave.

示例1

输入:

5
2 2 6 4 5

输出:

2 1 4 5 3

说明:

In the first round, the patience value of people who's still in the queue is $[2,2,6,4,5]$ . Their patience value and the queue is changed as the way follows:

$x_1:=x_1-1 \, \rightarrow \, [1,2,6,4,5]$ ;

$x_2:=x_2-2 \, \rightarrow \, [1,6,4,5]$ , and since $x_2$ is reduced to $0$ , the $2^{\rm{nd}}$ person leaves the queue;

$x_3:=x_3-2 \, \rightarrow \, [1,4,4,5]$ , after $2^{nd}$ person left, the rank of $3^{\rm{rd}}$ person has changed to $2$ , so his patience value is reduced by $2$ in this round;

$x_4:=x_4-3 \, \rightarrow \, [1,4,1,5]$ ;

$x_5:=x_5-4 \, \rightarrow \, [1,4,1,1]$ .

In the second round, their patience value is reduced as the way follows:

$x_1:=x_1-1 \, \rightarrow \, [4,1,1]$ , the $1^{\rm{st}}$ person leaves the queue;

$x_3:=x_3-1 \, \rightarrow \, [3,1,1]$ ;

$x_4:=x_4-2 \, \rightarrow \, [3,1]$ , the $4^{\rm{th}}$ person leaves the queue;

$x_5:=x_5-2 \, \rightarrow \, [3]$ , the $5^{\rm{th}}$ person leaves the queue.

And finally, in the fifth round, the patience value of $3^{\rm{rd}}$ person is reduced to $0$ , and he leaves the queue. So the order in which $n$ people leave in the example is $[2,1,4,5,3]$ .

上次编辑到这里，代码来自缓存点击恢复默认模板

C 解法, 执行用时: 12ms, 内存消耗: 368K, 提交时间: 2021-05-19 21:29:04

#include<stdio.h>
#define ll long long 
const int maxn=1003;
int n;
const ll inf_ll=0x7FFFFFFFFFFFFFFF; 
ll a[maxn];
int b[maxn];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	int sum=0;
	while(sum<n){
		ll minn=1e18+10;
		ll cnt=1;
		for(int i=1;i<=n;++i){
			if(b[i])
                continue;
			if(minn>(a[i]+cnt-1)/(cnt)){
				minn=(a[i]+cnt-1)/(cnt);
			}
			cnt++;
		}
		cnt=1;
		for(int i=1;i<=n;++i){
			if(b[i])continue;
			a[i]-=(minn-1)*(cnt);
			cnt++;
		}
		cnt=1;
		for(int i=1;i<=n;++i){
			if(b[i])continue;
			a[i]-=(cnt);
			if(a[i]<=0){
				printf("%d ",i);
				sum++;cnt--;
				b[i]=1;
			}
			cnt++;
		}
	}
}

C++(clang++11) 解法, 执行用时: 11ms, 内存消耗: 416K, 提交时间: 2021-05-11 14:36:25

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T[1001];
ll M[1001];
int main(){
  int n;
  int tot=0;
  scanf("%d",&n);
  for(int i=1;i<=n;i++)scanf("%lld",&T[i]);
  while(1){
  	if(tot==n)break;
    ll ma=1e18+1;
    for(int i=1;i<=n;i++){
      if(T[i]==-1)continue;
      ll s=ceil(T[i]*1.0/(i-M[i]));
	  ma=min(ma,s);
	}
	int k=0;
	for(int i=1;i<=n;i++){
        if(T[i]==-1)continue;
	  T[i]-=ma*(i-M[i]);
	  T[i]+=k;
	  M[i]+=k;
	  if(T[i]<=0){
	  	printf("%d ",i);
	  	T[i]=-1;
	  	k++;
	  	tot++;
	  }
	}
  }
    return 0;
}