洛谷P14171题解

分析

题意

一群小朋友围成一圈玩丢手绢游戏，每个小朋友都要把手绢放到某个位置。我们需要统计每个小朋友身后被放了多少次手绢（也就是人气值），最后找出人气最高的那些小朋友，按编号从小到大输出他们的号码。

位置计算：正数表示顺时针数几个位置，负数表示逆时针数几个位置，$0$ 就是自己身后。因为是围成一圈，所以需要处理好循环的情况。

思路

首先得搞清楚每个小朋友把手绢放到了谁身后。比如第 $i$ 个小朋友，根据给出的 $a_i$，我们要算出具体是哪个编号的小朋友。

然后计算位置时，因为是圆圈，所以需要用取模运算来处理。不过要注意负数的情况，比如当计算结果为负数时，得调整成有效的正数编号。

再用一个数组来记录每个小朋友的人气值，每确定一个手绢的位置，就给对应位置的人气值加 $1$。

最后找出人气值的最大值，然后把所有达到这个最大值的小朋友编号按顺序输出。

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 100;
int a[MAXN], cnt[MAXN];
int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        int x = i + a[i] - 1;
        x %= n;
        if (x < 0) x += n;
        int pos = x + 1;
        cnt[pos]++;
    }
    int m = *max_element(cnt + 1, cnt + n + 1);
    bool flag = 1;
    for (int i = 1; i <= n; i++) {
        if (cnt[i] == m) {
            if (flag) {
                cout << i;
                flag = 0;
            } 
            else cout << ' ' << i;
        }
    }
    return 0;
}