P1996 约瑟夫问题

题目背景

约瑟夫是一个无聊的人!!!

题目描述

n个人(n<=100)围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,……依次类推,直到所有的人都出圈,请输出依次出圈人的编号.

输入输出格式

输入格式:

n m

输出格式:

出圈的编号

输入输出样例

输入样例#1:

10 3

输出样例#1:

3 6 9 2 7 1 8 5 10 4

说明

你猜,你猜,你猜猜猜......

猜不着吧,我也不告诉你!!!‘

我确信我的是对的

但是不知道为什么会超时

跟填涂颜色那题一样

明明在自己机子上秒出但是超时??

 1 #include<cstdio>
 2 #include<cstring>
 3 const int MAXN=10001;
 4 int vis[MAXN];
 5 int flag=0;
 6 int main()
 7 {
 8     int n,m;
 9     scanf("%d%d",&n,&m);
10     int tot=0;
11     int i=1;//有几个人报数 
12     int now=1;// 正在枚举第几个人 
13     while(tot<n)
14     {
15         while(vis[now+1]==0&&i<m&&now<n){i++;now++;}
16         if(i==m)
17         {
18             tot++;
19             i=0;
20             vis[now]=1;
21             printf("%d ",now);
22             continue;
23         }
24         while(vis[now+1]!=0)
25         {now=now++;if(vis[now]==0)i++;}
26         
27         if(now==n)now=0;
28     }
29     return 0;
30 }
 1 #include<iostream>
 2 using namespace std;
 3 int n,m;
 4 bool out[102];//out[i]:记录点i是否已经出圈,为true则已出圈,之后循环需要跳过i;false则表示还未出圈 
 5 int main()
 6 {
 7     scanf("%d%d",&n,&m);
 8     int cnt=0,now=0,tot=0;//cnt:当前数的数  now:当前轮到第几个人   tot:已出圈人数,用来在达到条件时结束循环(等于总人数n) 
 9     while(tot!=n)
10     {
11         cnt++;now++;
12         if(cnt==m+1)//循环处理,形成一个环 
13           cnt=1;
14         if(now==n+1)//同上 
15           now=1;
16         while(out[now])//当now这个人已经出圈时,应跳过now,直到找到下个未出圈的人(out[now]=false) 
17         {
18             ++now;
19             if(now==n+1)//形成环 
20               now=1;
21         }
22         if(cnt==m)//当前数到m,now出圈,总出圈人数+1 
23           out[now]=1,++tot,printf("%d ",now);
24     }
25     return 0;
26 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

Day2上午解题报告

预计分数:100+0+60=160 实际分数:100+0+60=160 mmpT1数据错了。。。 T1遭遇 题目描述 你是能看到第一题的 friends呢。 —...

46340
来自专栏机器学习算法与Python学习

长文 | 手把手教你如何使用python进行数据分析(最好将文章代码自己码一遍)

关键字全网搜索最新排名 【机器学习算法】:排名第一 【机器学习】:排名第二 【Python】:排名第三 【算法】:排名第四 原文 http://www.cnbl...

40050
来自专栏前端新视界

一道看似非常难的面试算法题

这是昨天面试百度时碰到的一道算法题:任意数分三组,使得每组的和尽量相等(感谢博友提供的关于该问题的相关资料 划分问题)。由于时间仓促,加之面试时头昏脑涨,这道题...

27280
来自专栏我的python

递归方法的理解

递归思想算是编程中比较常见但对初学者而言又有些难以理解的方法了。在leetcode上刷了几道题都用递归思想成功解决后觉得应该贯彻互联网的开源共享精神,总结一下自...

13900
来自专栏Albert陈凯

MapReduce编程思想通俗理解

综述 Map(映射)与Reduce(化简)来源于LISP和其他函数式编程语言中的古老的映射和化简操作,MapReduce操作数据的最小单位是一个键值对。用户在使...

32280
来自专栏take time, save time

你所能用到的数据结构(三)

三、对于效率提高的初次尝试     对于最自然的几种排序算法,数学家们开始思考如何提高排序算法的效率,可以通过数学证明出来如果想达到这个目的,必须想办法将相距...

29470
来自专栏专知

关关的刷题日记78 – Leetcode 69. Sqrt(x)

关关的刷题日记78 – Leetcode 69. Sqrt(x) 题目 Implement int sqrt(int x). Compute and retur...

36460
来自专栏张俊红

Python面向对象编程

24050
来自专栏算法修养

HYSBZ 2160 拉拉队排练(回文树)

2160: 拉拉队排练 Time Limit: 10 Sec  Memory Limit: 259 MB Submit: 825  Solved: 324 [...

35970
来自专栏C语言及其他语言

[每日一题]最多约数问题(1228)

本次的题目正确率可是低到了一个境界呢!快来试试吧! 题目描述 正整数x 的约数是能整除x 的正整数。正整数x 的约数个数记为div(x)。例如,1,2, 5...

41160

扫码关注云+社区

领取腾讯云代金券