问题 A: DS循环链表—约瑟夫环(Ver. I - A)
时间限制: 1 Sec 内存限制: 128 MB
提交: 269 解决: 132
[提交][状态][讨论版]
题目描述
N个人坐成一个圆环（编号为1 - N），从第S个人开始报数，数到K的人出列，后面的人重新从1开始报数。问最后剩下的人的编号。
例如：N = 3，K = 2，S = 1。2号先出列，然后是1号，最后剩下的是3号。
要求使用循环链表实现。
输入
第一行输入t，表示有t个测试用例；
第二行起，每行输入一组数据，包括3个数N、K、S，表示有N个人，从第S个人开始，数到K出列。(1 <= N <= 10^6，1 <= K <= 10, 1 <= S <= N)
输出
出列的人的编号
样例输入
2 13 3 1 3 2 1
样例输出
3 6 9 12 2 7 11 4 10 5 1 8 13
2 1 3
#include<iostream> using namespace std; class ListNode { int data; ListNode *next; friend class linklist; }; class linklist { int len; ListNode *head; public: int n, k, s; linklist() { head = new ListNode(); } ~linklist() { delete head; } void createlist() { len = n; ListNode *p, *q; p = head; for (int i = 1; i <= n; i++) { q =new ListNode(); q->data = i; p->next = q; p=p->next; } p->next = head; } void gg() { ListNode *p,*q; p = head; for (int i = 0; i < s - 1; i++) { p = p->next; } while (len) { if (p->next == head) p = p->next; q = p->next; for (int i = 0; i < k - 1; i++) { p = p->next; if (p->next == head) p = p->next; } q = p->next; cout << q->data << " "; p->next = q->next; delete q; len--; } cout << endl; } }; int main() { int t; linklist list; cin >> t; while (t--) { int N, K, S; cin >> N >> K >> S; list.n = N; list.k = K; list.s = S; list.createlist(); list.gg(); } }
