洛谷P1145 約瑟夫

題目描述

n個人站成一圈，從某個人開始數數，每次數到m的人就被殺掉，然后下一個人重新開始數，直到最后只剩一個人。現在有一圈人，k個好人站在一起，k個壞人站在一起。從第一個好人開始數數。你要確定一個最小的m，使得在第一個好人被殺死前，k個壞人先被殺死。

感謝yh大神指出樣例數據的錯誤。

輸入輸出格式

輸入格式：

?

一個k，0<k<14

?

輸出格式：

?

一個m

?

輸入輸出樣例

輸入樣例#1：

3

輸出樣例#1：

5

輸入樣例#2：

4

輸出樣例#2：

30

說明

0<k<14

分析：正解就是暴力.只要稍微優美那么一點點就能過了，最最最樸素的暴力就是枚舉m，然后一位一位地挪，非常慢，正確的方法是直接取模，判斷是不是壞人，每一個m最多走k次就會結束游戲，每次刪除一個人后把起點變一下，模數變一下就好了.需要注意的一點是每個人的下標要從0開始，不然取模的時候可能會得到0，然后就炸了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;int k,m = 1,beginn = 1;
bool flag = false,flag2 = false;bool check(int mod)
{int t = (beginn + m - 1) % mod;if (t >= k){beginn = t;return true;} return false;
}int main()
{scanf("%d",&k);m = k;while (1){beginn = 0;flag2 = 0;for (int i = 0; i < k; i++){if (!check(2 * k - i)){flag2 = 1;break;}}if (!flag2)break;m++;}printf("%d\n",m);return 0;
}

?