约瑟夫问题

也许更好地阅读体验

D e s c r i p t i o n \mathcal{Description} Description

经典的约瑟夫问题
一开始有 n n n 个人围成一个圈,他们的编号从 0 0 0 n 1 n-1 n1, 从 1 1 1 开始顺时针报数, 报出 m m m 的人被机关处决.
然后下一个人再从 1 1 1 开始报数, 直到只剩下一个人.
问最后剩下的人的编号.

n 1 0 18 , <mtext>   </mtext> m 1000 n\leq 10^{18},\ m\leq 1000 n1018, m1000

S o l u t i o n \mathcal{Solution} Solution

那些算法书总是把约瑟夫问题作为链表的例题来讲,初学者接触链表时还不会递推,于是一直以为只是一道链表题…

这么大的数据,当然不能链表模拟
考虑递推,还是那句话,递推的东西总是有联系的
递推时往往假设一个状态是已知的,然后试图推另一个状态,如果有递推式的话,我们就只要将最简单的状态手动求出即可
假设现在有 n n n个人,第一个被处决的人的编号肯定是 k = ( m 1 ) % n k=(m-1)\%n k=(m1)%n
当编号为 k k k的人被处决后,接下来我们认为是从原编号为 k + 1 k+1 k+1的人开始重新编号,然后就是一个 n 1 n-1 n1个人的约瑟夫问题了
当然,这 n 1 n-1 n1个人的答案肯定不是最终答案,因为他是重新编号后的答案,所以我们要将其恢复原编号
因为新编号为 0 0 0的人前面有 m 1 m-1 m1个人,也就是编号左移了 m m m,所以最终的答案应该要加上 m m m
f [ n ] f[n] f[n]为长度为 n n n的最后剩下的人的编号
则有 f [ n ] = ( f [ n 1 ] + m ) % n f[n]=(f[n-1]+m)\%n f[n]=(f[n1]+m)%n

于是我们得到了一个 O ( n ) O(n) O(n)的做法
但这还不够
我们继续看这个方程,发现 n n n的答案可以被 h h h共用
只需要满足 f [ n ] + ( h n ) m &lt; n f[n]+(h-n)m &lt; n f[n]+(hn)m<n
也就是每次可以直接更新之后的 k = n f [ n ] m k=\frac{n-f[n]}{m} k=mnf[n]个长度的答案
于是就将复杂度大大降低了

C o d e \mathcal{Code} Code

/******************************* Author:Morning_Glory LANG:C++ Created Time:2019年09月01日 星期日 15时54分02秒 *******************************/
#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;
ll n,m,ans,now;
int main()
{
	scanf("%lld%lld",&n,&m);
	ans=0,now=1;
	while (now<n){
		ll inc=min((now-ans)/m,n-now);
		if (!inc)	inc=1;
		now=now+inc;
		ans=(ans+inc*m)%now;
	}
	printf("%lld\n",ans+1);
	return 0;
}

如有哪里讲得不是很明白或是有错误,欢迎指正
如您喜欢的话不妨点个赞收藏一下吧

全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务