数字炸弹【算法赛】

问题描述

蓝桥学院趁着暑假组织了一场出游，总共有 N 名学生参与本次出游。导游打算在这 N 名学生中选出一位学生成为小队长。所有学生都对这一队长身份十分感兴趣，导游为了平竞选，想出了一个数字炸弹游戏。

将学生从左往右依次编号设为 1,2,3,⋯,N。开始时的报数顺序为从左往右，即从编号为 1 的同学开始报数字 1，接下来编号为 2 的同学报数字 2，一直到编号为 N的同学报数字 N。接下来由编号为 N−1 的同学报数字 N+1，编号为 N−2 的同学报数字 N+2，即报数顺序变为从右往左，当报数来到编号为 11 的同学后，报数顺序又变为从左往右，直到某位同学报的数字为 M则报数停止。

导游让学生们找出报数为 M 的学生编号，最快回答出的学生将成为小队长。小蓝十分渴望得到这一身份，请你帮他快速计算答案。

输入格式

输入一行，包含两个正整数 N(2≤N≤10^5^) 和 M(1≤M≤10^9^)，分别表示学生人数和目标报数值。

输出格式

输出一个整数，表示报数为 M 的学生编号。

样例输入

1
5 11

样例输出

1
3

说明

对于 N=5，M=8，学生编号为 1,2,3,4,5。报数过程如下：

  • 编号 1 报 1，编号 2 报 2，编号 3 报 3，编号 4 报 4，编号 5 报 5（从左到右）。
  • 编号 4 报 6，编号 3 报 7，编号 2 报 8，编号 1 报 9（从右到左）。
  • 编号 2 报 10，编号 3 报 11（从左到右）。

当报到数字 11 时，编号为 3 的学生报数，因此输出 3。

解题思路

报数的顺序是先从左到右，然后再从右到左，我们可以就简单的看为

1 2 3 4 5 4 3 2 1 2 3…… （当N=5时）

观察数字之间的特殊点

我们可以看到它们这几个相邻数字的差值都是1，我们可以利用这个特点来让程序循环执行加1减1

程序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int main()
{
  int m,n,p=1,t=0;
  cout<<"请输入学生人数N和目标报数值M："<<endl;
  cin>> n >> m;

  for (int i = 0; i < m;i++){
    if(t == n) p = -1; //当轮到第t个学生也就是最后一个学生时，向左报数
    else if(t == 1) p = 1;  //当回到编号为1的学生时，向右报数
    t += p; //编号是t的学生
    }

  cout<< t;  
  return 0;
}