Timus #1521. War Games 2 – Pancake's Personal Website

题目：约塞夫问题。n个人排成一个圆圈开始报数，报数到k的人出列，输出该人在原队列的位置。

解析：
1. 直接for循环，利用vector和简单的数学计算
2. 线段树解约塞夫环

代码：
1. vector

#include<iostream>
#include<vector>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector <int> arr;
	for (int i = 0; i < n; i++)arr.push_back(i + 1);
	int position = 0;
	while (!arr.empty()) {
		position = (position + k - 1) % arr.size();
		cout << arr[position] << " ";
		arr.erase(arr.begin() + position);
	}
	return 0;
}

#include<iostream>

#include<vector>

using namespace std;

int main() {

int n, k;

cin >> n >> k;

vector <int> arr;

for (int i = 0; i < n; i++)arr.push_back(i + 1);

int position = 0;

while (!arr.empty()) {

position = (position + k - 1) % arr.size();

cout << arr[position] << " ";

arr.erase(arr.begin() + position);

}

return 0;

}

2. 线段树解约塞夫环

CSDN代码

发表回复

发表回复 取消回复

发表回复取消回复