当前位置:网站首页>[2018蓝桥杯决赛] D-约瑟夫环

[2018蓝桥杯决赛] D-约瑟夫环

2020-11-10 17:23:40 Fool_one

题解

  先看数据范围,n, k <= 1e6,如果采用队列解题,时间复杂度能达到 $O(n * k)$ 必定会超时。

       显然,这一题应该采用数学方法,可用 $O(n)$ 的时间复杂度解决,如何解决呢?

       我们先来看示意图:

  

  这实际上是一个递推关系,f[i] 表示有 i 个人,从 1 开始报数,最后出局人的编号,当报数为 k 的人即编号为 k - 1 的人出队时,此时只剩下 i - 1个人,而 f[i - 1] 表示有 i - 1个人,k 从 1 开始报数,最后剩下人的编号,显然从 1 开始报数的人,编号并非为 0 ,而变成了 k,而在递推的时候需要记录原来的编号则需要加上 k,则数学递推式为:

      f[i] = (f[i - 1] + k) % n。

#include <iostream>
using namespace std;

int n, m, ans = 0;

// 数学方法 
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        ans = (ans + m) % i;
    }
    cout << ans + 1 << endl;    
    return 0;
}

 

版权声明
本文为[Fool_one]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/xuwenchao/p/13954396.html