贴一篇博客，写的还行
经典约瑟夫问题的快速求解
除了循环链表模拟，和动态规划求解
还可以利用树状数组，树状数组的时间复杂度为O（n * (logn)^2）
算是非常快的了
而且不同于动态规划只能在报数长度一定的情况下解决约瑟夫问题。
树状数组可以在报数长度不定的情况下解决，相当于对模拟做了一个优化。a
emmmmmmmm......
首先，我们可以有这样递推的思路：不断加k模n，并减去其数字前走了的人即为当前人的真实编号（即是这一轮应踢走的人的编号），如何快速维护每个人其前走了的人的和，答案为树状数组。
现在模拟一下过程，假设有6个人，k=3（每报3个，走一个人）。
初始状态：1 2 3 4 5 6
用树状数组在每个人的位置加一，可得前缀和：1 2 3 4 5 6
现在1+2(其实是k-1)=3走了:1 2 4 5 6
用树状数组在3的位置减1，可得前缀和：1 2 2 3 4 5
再走了3+2=5，5%（6-1）=5（走了一个人，故6需减1）等等，此时并不是走了5，而是在树状数组中前缀和为5的数字，由上可知走了6：1 2 4 5
用树状数组在6的位置减1，可得前缀和：1 2 2 3 4 4
又按5+2=7，7%（6-2）=3，但这时在树状数组的前缀和中查找3，可见是第四个人的状态为3，故此回合走了4：1 2 5
用树状数组在4的位置减1，可得前缀和：1 2 2 2 3 3
又按3+2=5，5%（6-3）=2，在树状数组中查找二，可见即为2，
故此回合走了2：1 5，
前缀和改为：1 1 1 1 2 2
最后2+2=4，4%（6-4）=2，在树状数组中查找2，可见为5，
故最后只剩1了。
因为前缀和是单调的，所以查找可以用二分。
可得序列为：3 6 4 2 5 1
这个东西还挺有意思的，要是遇到需要求约瑟夫问题，但是报数长度不定可以用bit模拟，比循环链表不知道稳到哪去了
模板可以看一个例题
POJ - 2886
=.=贴题目
N children are sitting in a circle to play a game.
The children are numbered from 1 to N in clockwise order. Each of them has a card with a non-zero integer on it in his/her hand. The game starts from the K-th child, who tells all the others the integer on his card and jumps out of the circle. The integer on his card tells the next child to jump out. Let A denote the integer. If A is positive, the next child will be the A-th child to the left. If A is negative, the next child will be the (−A)-th child to the right.
The game lasts until all children have jumped out of the circle. During the game, the p-th child jumping out will get F(p) candies where F(p) is the number of positive integers that perfectly divide p. Who gets the most candies?
Input
There are several test cases in the input. Each test case starts with two integers N (0 < N ≤ 500,000) and K (1 ≤ K ≤ N) on the first line. The next N lines contains the names of the children (consisting of at most 10 letters) and the integers (non-zero with magnitudes within 108) on their cards in increasing order of the children’s numbers, a name and an integer separated by a single space in a line with no leading or trailing spaces.
Output
Output one line for each test case containing the name of the luckiest child and the number of candies he/she gets. If ties occur, always choose the child who jumps out of the circle first.
Sample Input
4 2
Tom 2
Jack 4
Mary -1
Sam 1
Sample Output
Sam 3
=.=贴代码
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<math.h>
#include<stdlib.h>
using namespace std;
const int maxn = 500050;
int bit[maxn]; //树状数组
char name[maxn][15];
int val[maxn];
int a[39]= {1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,
2520,5040,7560,10080,15120,20160,25200,27720,45360,50400,
55440,83160,110880,166320,221760,277200,332640,498960,500001};
int b[39]= {1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,
80,84,90,96,100,108,120,128,144,160,168,180,192,200,1314521};
int n;
int sum(int i)
{
int s = 0;
while(i > 0)
{
s+=bit[i];
i-=(i&-i);
}
return s;
}
void add(int i,int x)
{
++i;
while(i<=n)
{
bit[i] += x;
i += (i&-i);
}
}
int binary(int id)
{
int l = 0,r = n;
while(r-l>1)
{
int mid = (l+r) >> 1;
if(sum(mid) <= id) l = mid;
else r = mid;
}
return l;
}
int main()
{
int k;
while(~scanf("%d%d",&n,&k))
{
--k;
memset(name,0,sizeof(name));
memset(val,0,sizeof(val));
memset(bit,0,sizeof(bit));
for(int i=0;i<n;i++)
{
scanf("%s %d",name[i],&val[i]);
add(i,1);
}
int candy = -1;
int iu = 0,Max = 0,p = 0;
while(a[iu] <= n)
iu++;
p = a[iu-1];
Max = b[iu-1];
for(int i=1;i<p;i++)
{
add(k,-1);
int mod = n-i;
int id = sum(k) + val[k] + (val[k]>0?-1:0);
id = (id%mod + mod)%mod;
k = binary(id);
}
printf("%s %d\n",name[k],Max);
}
}
网友评论