苏州OJ c002: 双向约瑟夫

旧城等待， 2022-08-14 04:55 8阅读 0赞

**内容：**

【问题描述】  
有n个人围坐在一个圆桌周围，把这n个人依次编号为1~n。从编号为1的人开始顺时针报数，报到m1的人出列；然后逆时针方向报数，报到m2的人出列。问最后谁出列？  
【输入】  
输入数据仅一行，包含三个用空格隔开的正整数n，m1和m2。  
【输出】  
数据数据仅一行，包含一个正整数k，即最后一个人的序号。  
【样例】  
输入  
10 5 7  
输出

看到题目的时候一开始就知道应该用循环队列来解决，然后自己就开始写了个循环队列的类。。

后来发现这样反而把题目给复杂化了，所以下面贴两个代码，一个是之前给复杂化了的代码，一个是比较简单化的。

一开始写的：

#include <iostream>
    using namespace std;
    
    struct Node {
    	int x;
    	Node* prev;
    	Node* next;
    
    	Node(int val, Node* pr, Node* ne)
    		:x(val), prev(pr), next(ne) {}
    };
    
    class CirculateList {
    
    public:
    	CirculateList() { first = last = NULL; }
    	~CirculateList() {
    		Node* tmp = first;
    		while (tmp != last) {
    			first = first->next;
    			delete tmp;
    			tmp = first;
    		}
    		delete tmp;
    	}
    
    	void push(const int& x) {
    		if (first == NULL)  {
    			first = new Node(x, first, first);
    			first->next = first;
    			first->prev = first;
    			last = first;
    		}
    		else {
    			Node* newNode = new Node(x, last, first);
    			last->next = newNode;
    			first->prev = newNode;
    			last = newNode;
    		}
    	}
    
    	void remove(Node* node) {
    		Node* tmp = first;
    		if (node == first) first = first->next;
    		if (node == last) last = last->prev;
    
    		node->prev->next = node->next;
    		node->next->prev = node->prev;
    	}
    	// 顺序删除
    	Node* inOrder(int num, Node* node) {
    		Node* delNode = node;
    		while (--num) {
    			delNode = delNode->next;
    		}
    		Node* tmp = delNode->prev;
    		remove(delNode);
    		return tmp;
    	}
    	// 逆序删除
    	Node* postOrder(int num, Node* node) {
    		Node* delNode = node;
    		while (--num) {
    			delNode = delNode->prev;
    		}
    		Node* tmp = delNode->next;
    		remove(delNode);
    		return tmp;
    	}
    	// 是否就剩下一个了
    	bool isOK() {
    		return ((first == last) && (first != NULL));
    	}
    
    	int front() {
    		return first->x;
    	}
    
    	Node* getFirst() {
    		return first;
    	}
    
    private:
    	Node* first;
    	Node* last;
    };
    
    int main()
    {
    	
    	CirculateList clst;
    	
    	int n, m1, m2;
    	cin >> n >> m1 >> m2;
    	// 添加进去
    	for (int i = 1; i <= n; ++i) {
    		clst.push(i);
    	}
    	// count用来标记是顺时针还是逆时针删除
    	int count = 1;
    	Node* node = clst.getFirst();
    	while (!clst.isOK()) {
    		if (count % 2 == 1) {
    			node = clst.inOrder(m1, node);
    		}
    		else {
    			node = clst.postOrder(m2, node);
    		}
    		++count;
    	}
    	cout << clst.front();
    
    	return 0;
    }

后来写的：

#include <iostream>
    using namespace std;
    
    struct Node {
    	int x;
    	Node* prev;
    	Node* next;
    
    	Node(int val, Node* pr, Node* ne)
    		:x(val), prev(pr), next(ne) {}
    };
    
    int main()
    {
    	int n, m1, m2;
    	cin >> n >> m1 >> m2;
    	// 构造头,尾结点
    	Node* head = new Node(1, NULL, NULL);
    	head->next = head;
    	head->prev = head;
    	Node* last = head;
    	// n个人
    	for (int i = 2; i <= n; ++i) {
    		Node* t = new Node(i, last, head);
    		head->prev = t;
    		last->next = t;
    		last = t;
    	}
    	// tmp是用来移动的
    	// delNode是用来标记要删除的节点
    	Node* tmp = head;
    	Node* delNode;
    	int count = 1;
    	// 直到剩下一个节点
    	while (head != last) {
    		// 顺时针
    		if (1 == count % 2) {
    			for (int i = 1; i < m1; ++i) {
    				tmp = tmp->next;
    			}
    			if (tmp == head) head = head->next;
    			if (tmp == last) last = last->prev;
    	
    			tmp->prev->next = tmp->next;
    			tmp->next->prev = tmp->prev;
    			delNode = tmp;
    			tmp = tmp->prev;
    			delete delNode;
    		}
    		// 逆时针
    		else {
    			for (int i = 1; i < m2; ++i) {
    				tmp = tmp->prev;
    			}
    			if (tmp == head) head = head->next;
    			if (tmp == last) last = last->prev;
    	
    			tmp->prev->next = tmp->next;
    			tmp->next->prev = tmp->prev;
    			delNode = tmp;
    			tmp = tmp->next;
    			delete delNode;
    		}
    		++count;
    	}
    	cout << head->x;
    	delete head;
    
    	return 0;
    }