博客

题目链接:

年会抢玩偶游戏

题意：

n个人站成一排来抢m个小玩偶，规定每个人抢到的礼物不能比左右两边的人多两个或以上，赢得游戏的人拥有最多的玩偶，问第k个位置的人在赢得游戏时拥有多少玩偶？

分析：

设第k位置的人拥有玩偶数为p，为了使其赢得游戏，我们自然地想到让(k-1)~1位置的人玩偶数依次减1，(k+1)~n的依次减1，令s = k(k-1)/2-(n-k+1)(n-k)/2，即有np – r = m，但要确保p为整数，(m+r)需为n的倍数，所以前面的(k-1)~1的依次减1以及(k+1)~n的依次减1未必都能做到。因为第k个位置为胜者，其余n-1位置的人抢到的玩偶都较之少，所以最多遍历n次，每次将前面多减的1加回来即可。注意k可能越界


另：

题目输入描述有些问题，明明n、m、k均为正整数，样例中却存在k为0的情况，而且实测n、m、k均有为0 的case.

#include <iostream>

using namespace std;

int main()
{
    int n, m, k;
    cin >> n >> m >> k;
    if (n && (k>=1 && k<=n))
    {
        int s = ((n - k + 1)*(n - k) >> 1) + (k * (k - 1) >> 1); //*、+优先级大于>>
        for (int i = 0; i < n; i++)
        {
            if ((m + s - i) % n == 0)
            {
                cout << (m + s - i) / n << '\n';
                break;
            }
        }
    }
    else cout << "0" << '\n';
    return 0;
}