首页 > 其他分享 >P1145 约瑟夫

P1145 约瑟夫

时间:2023-03-16 23:46:02浏览次数:51  
标签:begin int 样例 约瑟夫 result P1145 find

P1145 约瑟夫

约瑟夫

题目描述

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

输入格式

一行一个整数 k。

输出格式

一行一个整数 m。

样例 #1

样例输入 #1

3

样例输出 #1

5

样例 #2

样例输入 #2

4

样例输出 #2

30

提示

0< k< 14。

提交答案

#include<cstdio>
using namespace std;
int i,find,k,m,begin;
int check(int remain)
{
    int result=(begin+m-1)%remain;
    if(result>=k){//判断出列的那个人
        begin=result;
        return 1;
    }
    else{return 0;}
}
int main(){
    scanf("%ld",&k);
    m=k;
    while(!find)
     {
        find=1;begin=0;//设置第一个
        for(i=0;i<k;i++)
        {
            if(!check(2*k-i))//如果判断好,就可以退出了……
            {
                find=0;break;
            }
        }
        m++;
    }
    printf("%d",m-1);//多加了一个,减回去
    return 0;
}

标签:begin,int,样例,约瑟夫,result,P1145,find
From: https://www.cnblogs.com/bujidao1128/p/17225098.html

相关文章

  • P1996 约瑟夫问题
    P1996约瑟夫问题约瑟夫问题题目描述n个人围成一圈,从第一个人开始报数,数到m的人出列,再由下一个人重新从1开始报数,数到m的人再出圈,依次类推,直到所有的人都出圈,请......
  • 【codevs1282】约瑟夫问题
    problemsolutioncodes//不好玩#include<iostream>usingnamespacestd;intn,m,a[30010],r,p;intmain(){cin>>n>>m;for(inti=1;i<=n;i++)a[i]=i;r......
  • ACM-ICPC 2018 沈阳赛区现场赛 K. Let the Flames Begin (约瑟夫环问题 n个人, 报数为k
     题意: n个人围成一个圈,从1开始报到第k个人出环,问第m个出环的人是谁,n、m、k<=1e18且min(m,k)<=2e6。题解:约瑟夫环的出队是有O(n)的递推算法的:f(n)=(f(n-1)+k-1)......
  • 数据结构-小孩出圈问题(约瑟夫环问题)
    假设有m个小孩,数到n的小孩出列,直到全部出去为止。使用环形链表解决约瑟夫环问题。packagecom.linkedlist;publicclassJosephuLinkeslist{publicstaticvoid......
  • POJ 2886(线段树+单点修改+约瑟夫环)
    DescriptionN childrenaresittinginacircletoplayagame.Thechildrenarenumberedfrom1to N inclockwiseorder.Eachofthemhasacardwithanon-zer......
  • 约瑟夫问题(洛谷P1996)
    问题描述:有n个人,编号为1~n,按顺序围成一圈,从第一个人开始报数,到第m个人出列,再由下一个人重新从1开始报数,数到m再出列,直到所有人都出列,依次输出所有出列的人的编号。输入:两......
  • 约瑟夫环问题——legend
    约瑟夫环问题:(一)问题:已知有n个人(编号为1,2,3...n)围坐在一个圆桌周围,从编号为k的人开始报数,数到m的那个人出队,出队的下一个位置的人继续从k开始数数,数到m的那个人继续......
  • 洛谷 P1996 约瑟夫问题
    问题简介:小朋友围城一圈,从1号开始报数,报到M的那位同学出局,然后下一位同学报1,循环上述过程直到所有同学出局。输出依次出局的小朋友的号码解题思路:没什么好说的,就是模拟,出局......
  • 约瑟夫环问题
    约瑟夫环问题百度百科中写道:"约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。"其可以理解成有一个[0..N-1]的数组,......
  • 单向循环链表-约瑟夫问题
    单向环形列表应用场景:约瑟夫环问题思路:创建第一个节点,让first指向该节点,并形成环状后面当我们每创建一个新的节点,就把该节点,加入到已有的环形链表中即可遍历环形链......