來(lái)源：牛客網(wǎng)：

題目描述

1st Academy is an international leadership training academy based in Kuala Lumpur. Every year, the company trains thousands of people to be supplied to companies around the world. To be fair amongst all the trainees, the company will do the selection process using numbering system. The trainees will choose a number from 1 to N, and one number is not limited to only one trainee. The N represents the total number of companies that request trainees from the academy. A number, M, would be picked at random, and the selection starts with a trainee whose number is 1, and then in every M’th people after that, wrapping around to 1 after N, and ignoring trainees already selected. For example, if N = 15 and M = 6, trainees would be selected in the order: 6, 12, 3, 10, 2, 11, 5, 15, 13, 9, 14, 4, 1, 8, 7. All the selected trainees except the last one (which is number 7) will be supplied to companies outside of Malaysia.
However, Leong preferred to stay and work in Malaysia. To him, there is no better place other than Malaysia. He does not mind being located anywhere as long it is Malaysia. As a friend of him, you could help him to choose a number that will save him from being located outside.
Input
輸入描述:
Input will consist of a series of lines, each line containing the number of companies (N) with 1 \leq N \leq 15001≤N≤1500, and a skipping value (M) with 1 \leq M \leq 501≤M≤50. The values will be terminated by a line consisting of double zeros (0 0) as shown in sample input output.
輸出描述:
Output will consist of a series of lines, one for each line of the input. Each line will consist of the number M according to the above scheme.
示例1
輸入
復(fù)制

15 6 550 23 0 0

輸出
復(fù)制

7 470

題意：

已知n個(gè)人(以編號(hào)1，2，3…n分別表示)圍坐在一張圓桌周圍。從編號(hào)為k的人開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人出列;他的下一個(gè)人又從1開(kāi)始報(bào)數(shù)，數(shù)到m的那個(gè)人又出列;依此規(guī)律重復(fù)下去，直到圓桌周圍的人全部出列。問(wèn)最后一個(gè)出列的人是多少號(hào)

題解：

經(jīng)典約瑟夫環(huán)問(wèn)題
我們看一下樣例：
15 6
依次出列的是：
6, 12, 3, 10, 2, 11, 5, 15, 13, 9, 14, 4, 1, 8, 7.
最后是7,7就是我們的答案
這個(gè)題麻煩在已經(jīng)出列的人不能再被算在里面
第一次6出列后，再往后數(shù)數(shù)時(shí)就不能再算6，那該怎么做?
我們可以這樣，當(dāng)指針指向第一個(gè)要出列的數(shù)6時(shí)，6出列后，
原本是：
1 2 3 4 5 6 7 8 9 …
更改為：
1 2 3 4 5 7 8 9…
讓6后面的每個(gè)數(shù)向前覆蓋，然后總量也從15變?yōu)?4，（第15位變成0）
指針也向前移動(dòng)，因?yàn)?已經(jīng)不存在了
一直模擬這個(gè)過(guò)程即可，當(dāng)只剩下兩個(gè)數(shù)，且存在有一個(gè)數(shù)已經(jīng)被移開(kāi)，那最后吃雞的數(shù)就是我們要的

代碼：

#include<bits/stdc++.h> using namespace std; const int maxn=2000; int pos[maxn]; int main() {int m,n;while(cin>>m>>n)//總?cè)藬?shù) 以n循環(huán){if(m==0||n==0)break;for(int i=1;i<=m;i++)pos[i]=i;//給每個(gè)數(shù)一個(gè)編號(hào)int temp=0;while(true){temp+=n;//temp%=m;//if(temp==0)temp=m;//指向最后一個(gè)人 for(int i=temp;i<m;i++)pos[i]=pos[i+1];//第temp的數(shù)不存在，編號(hào)前移pos[m]=0;//去掉一個(gè)人 m--; //人數(shù)少一temp--;if(pos[2]==0)break;//當(dāng)?shù)箶?shù)第二個(gè)數(shù)刪除以后 }cout<<pos[1]<<endl;} return 0; }

總結(jié)

以上是生活随笔為你收集整理的2020牛客国庆集训派对day2 AKU NEGARAKU的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。