URAL - 1794 J - Masterpieces of

这道题是组队赛上遇到的，我当时脑袋卡住了，写了个暴力，刚开始还写错了，后来知道双层循环暴力肯定会超时的时候，比赛已经结束了，过后听学长讲题的时候知道这个题其实直接用两个for循环，2n的复杂就可以做出来的。真的觉得我当时太智障了，这个题其实就是个水题。

题意大概就是老师要围着一个圆桌开一个主题课，让同学们写下他希望第几个发言，成绩好的希望先发言，成绩差的希望后发言，多一些准备时间，发言时间是按顺时针顺序，一个接一个，给1-n个同学编号，题目要求确定从哪个同学开始按照顺时针顺序发言，能够使得不满意的同学的人数最少。
我开始想的就是直接暴力枚举，遍历编号从1到n的人第一个发言所造成的不满的人数，找到最小的那个，并记录他的下标。然后输出下标就行了，然而这种想法肯定是会超时的。能A的想法是根据每一个人希望发言的顺序，找到此时第一个发言的人的下标m = i-a[i]+1，开一个vis数组vis[m]++,表示这个人被期望第一个发言的次数+1，最后只要遍历vis[1]到vis[n]中最大的数字，在输出它的下标就得到了最终答案。

代码如下：

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
int a[100010];
int vis[100010];
int main()
{
    int n,m;
    scanf("%d",&n);
    for(int i = 1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        m = i-a[i]+1;
        if(m<=0)
        {
            vis[m+n]++;
        }
        else
        {
            vis[m]++;
        }
        
    }
    int max = 0,k = 0;
    for(int i = 1;i<=n;i++)
    {
        if(vis[i]>=max)
        {
            max = vis[i];
            k = i;
        }
    }
    printf("%d\n",k);
}

好吧，后来队友告诉我这类问题叫做投票问题