约瑟夫问题
时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 65536 KByte
总提交 : 607 测试通过 : 57
比赛描述
约瑟夫问题是一个非常经典的问题，它的问题描述是：有 n 个人围成一圈，从第 1 个人开始，每次按顺时针方向向后选择第 m 个人，并将这个人出列。那么你能高效的算出出列的顺序吗？
输入
输入数据有多组，每组输入数据为一行，两个正整数 n和m (1<=n，m<=30000)
输出
每组输出只有一行，表示出列的顺序。每两个数字之间用一个空格分开。
样例输入
4 2
5 3
样例输出
2 4 3 1
3 1 5 2 4
很不错的一个题目，常用方法时数组或者链表模拟，会TLE，如果求最后剩下一个人的编号可以用数学方法计算。
思路
将每次出列的人拿掉，从左往右形成一个新的序列，每次从上一个出列的人所处为的位置考虑，找出下一个出列的人在新序列中的位置。
使用线段树或者树状树组可以很好的找到新序列中的第k个人的位置。
树状数组
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <math.h>
#include <bitset>
#include <ctype.h>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-9;
const int N = 3e4 + 5;
const int mod = 1e9 + 7;
int n, c[N];
inline int lowbit(int x)
{
return x&(-x);
}
void add(int x, int val)
{
while(x <= n)
{
c[x] += val;
x += lowbit(x);
}
}
int sum(int x)
{
int ans = 0;
while(x)
{
ans += c[x];
x -= lowbit(x);
}
return ans;
}
int m;
int main()
{
while(scanf("%d%d", &n, &m) != EOF)
{
memset(c, 0, sizeof(c));
for(int i = 1; i <= n; i++)
add(i,1);
int num = n, i = 0;
while(num > 1)
{
int j = (i+m-1)%num;
int p = j+1;
int l = 1, r = n, mid;
while(l <= r)
{
mid = (l+r) >> 1;
if(sum(mid) >= p) r = mid - 1;
else l = mid + 1;
}
printf("%d ",r+1);
add(r+1, -1);
i = j % (num-1);
num--;
}
int l = 1, r = n;
while(l <= r)
{
int mid = (l+r) >> 1;
if(sum(mid) >= 1) r = mid - 1;
else l = mid + 1;
}
printf("%d
", r+1);
}
return 0;
}
线段树
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <stack>
#include <string>
#include <math.h>
#include <bitset>
#include <ctype.h>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const double PI = acos(-1.0);
const double eps = 1e-9;
const int N = 3e4 + 5;
const int mod = 1e9 + 7;
int sum[N<<2];
int n,m;
int ans[N];
void build(int rt, int l, int r)
{
if(l == r)
{
sum[rt] = 1;
return;
}
int m = (l+r) >> 1;
build(rt << 1 , l, m);
build(rt << 1|1, m+1, r);
sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void update(int pos, int val, int rt, int l, int r)
{
if(l == r)
{
sum[rt] = 0;
return ;
}
int m = (l+r) >> 1;
if(pos <= m) update(pos, val, rt<<1, l, m);
else update(pos, val, rt<<1|1, m+1, r);
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
int query(int pos, int rt, int l, int r)
{
if(l == r)
return l;
int m = (l+r) >> 1;
if(pos > sum[rt<<1]) return query(pos - sum[rt<<1], rt<<1|1, m+1, r);
else
return query(pos, rt<<1, l, m);
}
int main()
{
while(EOF != scanf("%d%d", &n,&m))
{
build(1,1,n);
int len = n;
int i = 0;
int pos = 0;
while(len > 1)
{
int p = (i + m-1)%len;
ans[pos++] = query(p+1, 1, 1, n);
update(ans[pos-1], 0, 1, 1, n);
i = p%(len - 1);
len--;
}
ans[pos++] = query(1,1,1,n);
for(int i = 0; i < pos; i++)
{
if(i) printf(" ");
printf("%d", ans[i]);
}
printf("
");
}
return 0;
}