C. DS循环链表—约瑟夫环 (Ver. I - B)

题目描述

N个人坐成一个圆环（编号为1 - N），从第S个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。

例如：N = 3，K = 2，S = 1。2号先出列，然后是1号，最后剩下的是3号。

测试数据有多组，

每组包括3个数N、K、S，表示有N个人，从编号为S的人开始，数到K出列。

输入

测试数据有多组

每组包括3个数N、K、S，表示有N个人，从第S个人开始，数到K出列。(2 <= N <= 10^3，10^3 < K <= 10^9,  1 <= S <= N)

输出

出列的人的编号

输入样例1：

13 3 1
3 2 1

输出样例1：

3 6 9 12 2 7 11 4 10 5 1 8 13 
2 1 3 

AC代码：

#include <iostream>
using namespace std;
class node
{
public:int data;node* next;node():data(0),next(nullptr){}
};class linklist
{int len;node* head;
public:linklist(){head=new node;head->data=1;head->next=head;}void create(int n){node* tail=head;for(int i=2;i<=n;i++){node* p=new node;p->data=i;tail->next=p;p->next=head;tail=p;}tail->next=head;len=n;}void print(int k,int s){node* p=head;for(int i=1;i<s;i++){p=p->next;}while(len){int k1=k;k1=k1%len+len;for(int i=1;i<k1-1;i++){p=p->next;}node* q=p->next;cout<<q->data<<" ";p->next=q->next;delete q;p=p->next;len--;}cout<<endl;}};
int main()
{int n,k,s;while(cin>>n>>k>>s){linklist L;L.create(n);L.print(k,s);}return 0;
}