约瑟夫问题

推荐一个博客:约瑟夫环问题详解

约瑟夫问题

约瑟夫问题（有时也称为约瑟夫斯置换），是一个出现在计算机科学和数学中的问题。在计算机编程)的算法中，类似问题又称为约瑟夫环。

人们站在一个等待被处决的圈子里。 计数从圆圈中的指定点开始，并沿指定方向围绕圆圈进行。 在跳过指定数量的人之后，执行下一个人。 对剩下的人重复该过程，从下一个人开始，朝同一方向跳过相同数量的人，直到只剩下一个人，并被释放。

问题即，给定人数、起点、方向和要跳过的数字，选择初始圆圈中的位置以避免被处决。

简单约瑟夫环问题

给出n个人,间隔k个人,请这个人出列,一直这样下去,最后出列的人是谁?

递归解法

int fun(int n,int k){
    if(n==1)return 0;
    else return (fun(n-1,k)+k)%n;
}

下面来解释一下,假设

这里的fun都是对一个子问题的求解,强行解释为.可以去上面推荐的博客看看,有图会看得更清楚.

进阶约瑟夫环问题

题目传送门:Gym - 101955K

找出第M个出列的人

所以这是题解?(雾

第个出列的人最后所在的环是环,想知道算怎么来的?把代进去验证一下就好了啊(逃.其实是因为把第个人请出列之后就是一个的环了.所以前一个就是第个出列的人最后所在的环.

知道n-m+1的状态了,第个出列的人在环上是在(k-1)的位置上(像上面一样用子问题,倒推出主问题).所以用上面的直接跑?你想用O(n)跑?做你的大头梦去.

如果要跨环的时候还是要用上面的跑的,其他的可以来神仙优化一下,在一个环下,一次跑完它,而不要一步一步跑.这个是你在当前环最多能跑的长度.怎么算的?(留坑).然后把这个数除以就是你在这个环上一次能跑多少次.

为什么除以?因为你往回推的时候,别人已经把位置为的人给请出列了,所以你只能剩下的人在这个环里面,所以你除以这个才能知道你在这个环上能跑多少次.倒推到n环就要退出了,所以你在跑一整个环的时候,要取个min值,当前还能跑得环数和当前环能跑的次数.

用上面的算法的时候,要特判一下,的时候直接输出就好了,不然会RE.

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

int main() {
    int T;
    scanf ( "%d", &T );
    for ( int kase = 1; kase <= T; kase++ ) {
        long long n, m, k;
        scanf ( "%lld %lld %lld", &n, &m, &k );
        long long ans = 0;
        if ( k == 1 ) {
            printf ( "Case #%d: %lld\n", kase, m );
            continue;
        } else {
            ans = ( k - 1 ) % ( n - m + 1 );
            for ( long long i = n - m + 2; i <= n; ) {
                if ( ans + k >= i ) {
                    ans = ( ans + k ) % i;
                    i++;
                } else {
                    long long t = min ( n - i + 1, ( i - ans -2 ) / (k-1) );
                    ans += t * k;
                    i += t;
                }
            }
        }
        printf ( "Case #%d: %lld\n", kase, ans + 1 );
    }
    return 0;
}