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

Moanran · 2025-10-06 18:00:08 · 题解

题意简述

找到每个人丢手绢的次数，并找到最大值

思路分析

输入每个人丢手绢的位置，断环为链，每一次枚举到当前丢手绢的位置是否超过 1 或者 n ，整体复杂度是线性的

AC CODE

#include<iostream>
using namespace std;
int a[100005],cnt[100005];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=1;i<=n;i++)
    {
        int curr=i+a[i];
        if(curr<1) curr+=n;
        if(curr>n) curr-=n;
        cnt[curr]++;
    }
    int maxn=-1;
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,cnt[i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(maxn==cnt[i]) cout<<i<<" ";
    }
    return 0;
}