首页 > 其他分享 >【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)

【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)

时间:2024-09-09 12:51:43浏览次数:10  
标签:count 输出 出圈 int 题解 出队 P1996 洛谷 报数

约瑟夫问题

题目描述

【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)_出队 个人围成一圈,从第一个人开始报数,数到 【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)_出队_02 的人出列,再由下一个人重新从 【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)_出队_03 开始报数,数到 【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)_出队_02 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。

注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)_数组_05 名小朋友,而该题是全部出圈。

输入格式

输入两个整数 【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)_数组_06

输出格式

输出一行 【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)_出队 个整数,按顺序输出每个出圈人的编号。

样例 #1

样例输入 #1

10 3

样例输出 #1

3 6 9 2 7 1 8 5 10 4

提示

【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)_出队_08


思路

定义一个长度为 n 的一维数组 arr,用来表示队列。

首先,将 1~n 的数依次加入数组中。使用 count 记录当前报数的次数,使用 out 记录已经出队的人数,使用 f 记录是否是第一个出队的人,方便输出空格。

使用一个 while 循环,直到队列为空为止。在循环中,使用 for 循环遍历数组,对于已经出队的人,跳过。对于未出队的人,当报数次数 count 等于 m-1 时,输出其对应的数字,将其在数组中标记为已出队,并将 count 重置为 -1,out 加 1,f 设置为 1。重复此过程直到队列为空。


AC代码

#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;

int main()
{
    int n, m;
    int count = 0, out = 0, f = 0;

    cin >> n >> m;
    int arr[n];

    for (int i = 0; i < n; i++)
    {
        arr[i] = i + 1; // 初始化
        // cout << arr[i];
    }

    while (out < n)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[j] == 0)
            {
                continue; // 跳过
            }
            if (count == m - 1)
            {
                if (f == 1)
                {
                    cout << " ";
                }
                cout << arr[j];
                arr[j] = 0; // 出队
                count = -1;
                out++;
                f = 1;
            }
            count++;
        }
    }

    return 0;
}

标签:count,输出,出圈,int,题解,出队,P1996,洛谷,报数
From: https://blog.51cto.com/HEX9CF/11960189

相关文章

  • 题解 GZOI2023D2B【乒乓球】
    4s,512M题目描述Alice和Bob在打乒乓球,乒乓球比赛的规则是这样的:一场比赛中两位选手将进行若干局比赛,选手只需要赢得\(X\)局比赛就宣告其胜利;每局比赛中两位选手将进行若干盘比赛,选手只需要赢得\(Y\)盘比赛就宣告其胜利;每盘比赛中两位选手将进行乒乓球对决,有且仅有一位选......
  • AtCoder Beginner Contest 274 A~E 题解
    吐槽:这比赛名字为啥没有英文版。。。A-BattingAverage题目大意给定整数\(A,B\),输出\(\fracBA\),保留三位小数。\(1\leA\le10\)\(0\leB\leA\)分析签到题,使用printf或cout格式化输出即可。代码#include<cstdio>usingnamespacestd;intmain(){ inta,b; sc......
  • TOYOTA MOTOR CORPORATION Programming Contest 2023#1 (AtCoder Beginner Contest 29
    好久没写题解了,这就来水一篇。A-JobInterview题目大意给定一个长为\(N\)的字符串\(S\),由o、-、x组成。判断\(S\)是否符合下列条件:\(S\)中至少有一个o。\(S\)中没有x。\(1\leN\le100\)分析签到题。直接按题意模拟即可。代码#include<cstdio>usingn......
  • AtCoder Beginner Contest 318 G - Typical Path Problem 题解
    G-TypicalPathProblem题目大意给定一张\(N\)个点、\(M\)条边的简单无向图\(G\)和三个整数\(A,B,C\)。是否存在一条从顶点\(A\)到\(C\),且经过\(B\)的简单路径?数据范围:\(3\leN\le2\times10^5\)\(N-1\leM\le\min(\frac{N(N-1)}2,2\times10^5)\)\(1\leA......
  • UNIQUE VISION Programming Contest 2023 Christmas (AtCoder Beginner Contest 334)
    A-ChristmasPresent题目大意给定两个正整数\(B,G\)(\(1\leB,G\le1000\)且\(B\neG\)),判断哪个更大。分析模拟即可。代码#include<cstdio>usingnamespacestd;intmain(){ intb,g; scanf("%d%d",&b,&g); puts(b>g?"Bat":&qu......
  • 洛谷 P9754 [CSP-S 2023] 结构体 题解
    题目传送门洛谷博客CSDNCSP-S2023T3结构体题解基本思路本题主要考查编码能力,所以直接给出基本思路:由于可以递归式的创建元素,最多可以同时存在\(100^{100}\)个不同的基础类型的元素。即使算上最大地址的限制,元素的数量也能达到\(10^{18}\)。显然,依次构造每个元素,在空......
  • AT_agc027_f [AGC027F] Grafting 题解
    笑点解析:NOIP模拟赛把这题放在T3。因为每一个点只能动一次,答案一定\(\len\),所以我们分两种情况讨论:当答案小于\(n\)答案如果小于\(n\),那么一定有一个点是一直没有被动过的。我们枚举这个点,将无根树转化为两棵以这个点为根的有根树。我们将第一棵树和第二棵树同构的部分......
  • AtCoder Beginner Contest 254 A~E 题解
    A-LastTwoDigits题目大意给定正整数\(N\),求\(N\)的后两位。\(100\leN\le999\)输入格式\(N\)输出格式输出\(N\)的后两位,注意输出可能有前导0。样例\(N\)输出\(254\)54\(101\)01分析题目已经规定\(N\)是三位数,因此无需使用整数输入,直接将输入看成......
  • AtCoder Beginner Contest 258 A~Ex 题解
    D-Trophy题目大意有一个游戏,由\(N\)个关卡组成。第\(i\)个关卡由一个数对\((A_i,B_i)\)组成。要通过一个关卡,你必须先花\(A_i\)的时间看一次介绍。然后,用\(B_i\)的时间打通这个关卡。若想多次通过同一个关卡,则第一次需要看介绍,后面无需再看(即如果想打通第\(i\)关\(N\)次,则所......
  • AtCoder Beginner Contest 260 A~F 题解
    A-AUniqueLetter题目大意给定一个长度为\(3\)的字符串\(S\)。输出\(S\)中出现正好一次的字母(任意,如abc中,三个字母都可为答案)。如果没有,输出-1。数据保证\(S\)的长为\(3\),且由小写英文字母组成。输入格式\(S\)输出格式输出任意符合条件的答案。样例\(S\)输出......