題干：

N個人坐成一個圓環(huán)（編號為1 - N），從第1個人開始報數(shù)，數(shù)到K的人出列，后面的人重新從1開始報數(shù)。問最后剩下的人的編號。

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

Input

2個數(shù)N和K，表示N個人，數(shù)到K出列。(2?<=?N,?K?<=?10^6)

Output

最后剩下的人的編號

Input示例

3?2

Output示例

3

解題報告：

思路: 直接模擬的話O(n*k)的時間復(fù)雜度,按照套路來的話這樣的題一般是能找規(guī)律的; 我們先將n個人的編號改成0~n-1(別問為什么,套路而已),那么第1次報到號碼為k-1的人出列,圈里還剩下n-1個人 我們對比一下出列前后的編號:出列前: 0, 1, 2, 3, 4, 5, 6, ...k-2, k-1, k... n-1 出列后: n-k+1,..................n-2, , 1... n-k我們可以發(fā)現(xiàn)留下的人編號和留下來之前是一一對應(yīng)的,那么要是能找到對應(yīng)關(guān)系的話問題就迎刃而解了,不過現(xiàn)在數(shù)據(jù)太多了不好找 (偶就是這里找錯了規(guī)律然后只過了樣例),我們接著往下想想... 按照前面的規(guī)律,第n次報數(shù)時只有一個人,我們給他重新編號為0.前面我們也知道了某一輪某個人的編號和上一輪是對應(yīng)的,最后留下的人此時的編號為0, 那么只要我們由它上溯并找到它在第一輪時的編號答案就出來了啦~ 我們用f(x)表示最后留下來那個人在第n-x+1輪中的編號(這樣做我們就是由f(1)推f(n),更直觀一些,反之由f(n)推f(1)也是可以的),那么f(n)+1就是 最終答案了啦.很顯然有f(1)=0(因為此時只剩下一個人了嘛),接下來我們需要找到兩輪編號之間的映射關(guān)系,這個可以有枚舉k和x得到,這里就不寫枚舉 過程了啦~ 最后我們可以得到公式 f(x)=(f(x-1)+k)%x;

AC代碼：

#include <bits/stdc++.h> using namespace std;int main(void){int gg, n, k;cin >> n >> k;gg=0;for(int i=2; i<=n; i++){gg=(gg+k)%i; //前面說的f(x)只是為了我們更直觀地理解,其實直接用一個變量保存上一輪序號就可以了}cout << gg+1 << endl;return 0; }

轉(zhuǎn)自https://www.cnblogs.com/geloutingyu/p/6202200.html

總結(jié)

以上是生活随笔為你收集整理的【51nod - 1073】约瑟夫环问题模板的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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