华师一附中OI组

标题: P1145 约瑟夫 [打印本页]

---

作者: admin    时间: 2018-10-15 08:26
标题: P1145 约瑟夫
https://www.luogu.org/problemnew/show/P1145

题目描述
n个人站成一圈，从某个人开始数数，每次数到m的人就被杀掉，然后下一个人重新开始数，直到最后只剩一个人。现在有一圈人，k个好人站在一起，k个坏人站在一起。从第一个好人开始数数。你要确定一个最小的m，使得在第一个好人被杀死前，k个坏人先被杀死。

感谢yh大神指出样例数据的错误。

输入输出格式
输入格式：
一个k(0<k<14)
输出格式：
一个m
输入输出样例
输入样例#1：
3
输出样例#1：
5
输入样例#2：
4
输出样例#2：
30
说明
0<k<14

---

作者: admin    时间: 2020-7-11 08:26
题目的规模不大，k才14，我们用最直观的模拟穷举大法来做，复习下标准的约瑟夫：

1. #include<iostream>
   
2. using namespace std;
   
3. int a[10];
   
4. int i,s,j;
   
5. int main()
   
6. {
   
7.         int m=8,n=5;
   
8.         for (i=1; i<=m; i++) a[i]=1; ///初始都在圈内
   
9.         i=s=j=0;
   
10.         while (j<=m-1)
    
11.                 {
    
12.                         i++;
    
13.                         if (i>m) i=1;///围圈
    
14.                         s=s+a[i];///报数
    
15.                         if (s==n)
    
16.                                 {
    
17.                                         a[i]=0;//出圈
    
18.                                         s=0;
    
19.                                         cout<<i<<' ';
    
20.                                         j++;///+1
    
21.                                 }
    
22.                 }
    
23.         
    
24.         return 0;
    
25. }
    
26. /// m=8 n=5 k=3
    

复制代码

我们这个m=2k，不需要所有的人都出去，只需要出去k个人就可以了，所以第10行while(j<=m-1)就应该是j<=k-1,
在while退出州我们加一段代码检测是否都符合条件：看看前面k个人，就是1-k是否还在圈内，这个可以最直观的通过计算a1到ak的和是否等于k来判断，
然后类似反约瑟夫，枚举n，显然，n不可能<=k，想想为什么，（若n<k,则第一个出去的人的序号肯定小于k）

---

作者: admin    时间: 2020-7-11 13:06
这么做交上去只对了三组，其他的都是潮超时

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2