MENU

逆向思维编程题:消灭老鼠

• April 14, 2020 • Read: 90 • 编程问题

问题描述

有一只狡猾的老鼠,在一个环形的田埂上挖了n个老鼠洞,这些洞也是连接为一个环状,我们要用泥土填满这些鼠洞,老鼠从第0号洞开始出现(第0号洞不填),然后依次按每间隔m个洞出现一次。我们要跟在老鼠后面,当老鼠出现后填补上刚刚出现的洞。我们需要计算出老鼠最后出现那个洞(即剩下最后一个洞没有被我们填上时,这个洞的序号)。

输入

输入的第一行为了两个整数n(n<=300000)、m,n表示一共有n个老鼠洞,m表示老鼠每隔m个洞出现。

输出

输出老鼠最后出现的那个洞的序号。

样例

样例输入

5 2
8 3

样例输出

3
7

提示

第一个测试数据5 2的填洞顺序:2,4,1,0
第二个测试数据8 3的填洞顺序:3,6,1,5 ,2,0,4

思路解析

创建一个长度为洞个数的数组,用来记录该洞是否被填(0未填,1已填),并且数组的序号(0,1,2…)可以表示洞序号,循环m次,m次后那个洞应该被填上,标记为1,再次循环……标记为1,直到数组只剩下一个0,输出该0的序号

#include<stdio.h>
#include<stdlib.h>
int main(){
    int HoleNum,SkipNum;  //HoleNum洞的个数、隔SkipNum出现一次
    scanf("%d%d",&HoleNum,&SkipNum);  //输入数据
    int HoleNumCounter;   //记录剩余洞个数
    HoleNumCounter=HoleNum;
    int GoThroughHole=0;   //记录每次走过的洞个数
    int HoleStatus[HoleNum]; //记录洞是否被填上,0表示未填上
    for(int i=0;i<HoleNum;i++) HoleStatus[i]=0;
    int NowId; NowId=0;   //记录当前走到的洞的序号
    while(HoleNumCounter!=1){ //当洞个数剩余1退出算法
        GoThroughHole=0;  //每次开始走,走过的洞个数为0
        while(GoThroughHole!=SkipNum) {
            if(++NowId==HoleNum) NowId=0;
            if(HoleStatus[NowId]==0)
                GoThroughHole++;
        }
        HoleStatus[NowId]=1;  //走完步数,记录为已走
        HoleNumCounter--;
    }
    for(int i=0;i<HoleNum;i++)
        if(HoleStatus[i]==0) printf("%d",i);
    return 0;
}
Archives QR Code Tip
QR Code for this page
Tipping QR Code
Leave a Comment

2 Comments
  1. J J

    老鼠药一放,就ok

    1. @J你来,23333