题解：P14171 【MX-X23-T1】丢手绢

No_coding_extra · 2025-10-06 18:14:23 · 题解

题目大意：

传送门

对于第 i 个小朋友，以下规则记录下了数字 a_i：

• 若 a_i>0，将手娟放在从自己开始顺时针数 a_i 个位置的小朋友身后。
• 若 a_i<0，将手娟放在从自己开始逆时针数 -a_i 个位置的小朋友身后。
• 若 a_i=0，放在自己后面的啦。

按人气值从小到大排序，输出人气值最大的小朋友 ::::info[人气值] 规定人气值为身后被放手绢的次数。 ::::

思路：

这还有思路？直接模拟即可。

• 若 a_i>0，手绢放在第 i+a_i 小朋友身后。当然，若 i+a_i>n，说明小朋友已经转了一圈了，则手绢放在第 i+a_i-n 小朋友身后。
• 若 a_i<0，手绢放在第 i+a_i 小朋友身后。当然，若 i+a_i<1，说明小朋友已经转了一圈了，则手绢放在第 i+a_i+n 小朋友身后。
• 若 a_i=0，则放在自己后面的啦。

最后，用一个数组记下来第 i 个小朋友的人气值，将按人气值从小到大排序即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,x,a[N],maxn;
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        int t;
        if(x>0){
            t=i+x;
            if(t>n) t-=n;
        }
        else if(x<0){
            t=i+x;
            if(t<1) t+=n;
        }
        else{
            t=i;
        }
        a[t]++;
    }
    for(int i=1;i<=n;i++) maxn=max(maxn,a[i]);
    for(int i=1;i<=n;i++){
        if(a[i]==maxn) cout<<i<<" ";
    }
    return 0;
}

后记：

时间复杂度：O(N)。

空间复杂度：O(N)。

题解有问题可以私信哈！无耻地要个赞。