题目地址:http://vjudge.net/problem/UVALive-3882
先想想经典的约瑟夫,不去理m:
题目就是求f[n],即n个人中最后剩的人的标号是f[n](最初的编号)
为了方便,下标从0开始,
正常的思路就是 0~n个人,删去第k个,在0~n-1个人,删去第k个,即每次将第k个人移出队列中,然后再重新编号
因为这样意味着每次去掉下标为k-1的后要以k个为第一个,重新编号,所以要知道重新编号前,重新编号后,这两者编号有什么关系
设y=k;
y -> 0
y+1 ->1
y+2 ->2
...
...
y-2 -> n-2
即f[n-1]+y->f[n]
可以看出:n-1个人的位置映射到n个人的位置就是(x+k)%n
所以,有:
f [1]=0;
f [n] =(f [n-1]+k) %n; (f[n]一直保存一开始元素的编号,而不是改变编号后的编号)
再会过来看看怎么处理m:
在最后一步时,f[n]=(f[n-1]+m)%n 就好了
因为下标从零开始,所以ans+1;
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<=(b);++i)
#define REPD(i,a,b) for(int i=a;i>=(b);--i)
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
const int maxn=10000+3;
int f[maxn];
int main(int argc, char const *argv[])
{int n,k,m;while(scanf("%d%d%d",&n,&k,&m)==3&&(n+k+m)){f[1]=0;REP(i,2,n-1) f[i]=(f[i-1]+k)%i;f[n]=(f[n-1]+m)%n+1;printf("%d\n", f[n]);}return 0;
}