年会抢玩偶游戏

  • Post author:
  • Post category:其他


题目链接:

年会抢玩偶游戏

题意:

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;
}



版权声明:本文为zhui_xiuge原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。