🎯美团笔试-空间回廊

⭐ 孟应杰的网站: myj.im ⭐

📌题目描述：

有一款叫做空间回廊的游戏，游戏中有着n个房间依次相连，如图，1号房间可以走到2号房间，以此类推，n号房间可以走到1号房间。

这个游戏的最终目的是为了在这些房间中留下尽可能多的烙印，在每个房间里留下烙印所花费的法力值是不相同的，已知他共有m点法力值，这些法力是不可恢复的。

小明刚接触这款游戏，所以只会耿直的玩，所以他的每一个行动都是可以预料的：

1.一开始小明位于1号房间。
2.如果他剩余的法力能在当前的房间中留下一个烙印，那么他就会毫不犹豫的花费法力值。
3.无论是否留下了烙印，下一个时刻他都会进入下一个房间，如果当前位于i房间，则会进入i+1房间，如果在n号房间则会进入1号房间。
4.当重复经过某一个房间时，可以再次留下烙印。

很显然，这个游戏是会终止的，即剩余的法力值不能在任何房间留下烙印的时候，游戏终止。请问他共能留下多少个烙印。

输入

输入第一行有两个正整数n和m，分别代表房间数量和小明拥有的法力值。(1<=n<=100000,1<=m<=10^18)
输入第二行有n个正整数，分别代表1~n号房间留下烙印的法力值花费。(1<=a_i<=10^9)

输出

输出仅包含一个整数，即最多能留下的烙印。

样例输入

4 21
2 1 4 3

样例输出

9

提示

样例解释：
显然是所有房间都留下两个烙印，然后剩下1点法力值，仅能在2号房间再留下一个烙印.

⌨代码实现

#include<iostream>
using namespace std;

int main(){
    //输入房间数量m，小明拥有的法力值n
    int n, m;
    cin >> n >> m;
    //输入每个房间消耗的法力值
    int arr[n];
    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }
    //定义两个变量，cnt用来计数，记录留下的烙印数
    //sign,为设立的标志，当小明在一圈中消耗过法力值，标志位置为1，
    //如果一圈下来sign=0，那么代表这一圈小明没有消耗法力值，那么就可以结束循环了。
    int cnt = 0;
    int sign = 0;
    //循环开始，因为不知道要循环多少遍，所以中间参数为空
    for(int i = 0;  ; i++ ){
        //如果法力值大于当前格子的法力值
        if( m >= arr[i]){
            m = m - arr[i]; //法力值减去当前格子的法力值
            cnt++;          //烙印数+1
            sign = 1;       //本圈消耗了法力值，sign=1
        }
        //当i = n - 1，说明一次循环结束，如果sign=1，则需要进行下一轮循环
        //那么就把sign归0，有因为结束时会有i++，所以i=0-1，那么就开启新一轮循环
        if((i == n - 1) && (sign == 1)){
            sign = 0;
            i = 0-1;
        }
        //当i = n - 1，循环结束，sign=0，则不需要继续循环，直接跳出死循环。
        else if((i == n - 1) && (sign == 0)){
            break;
        }
    }
    cout << cnt << endl;
    return 0;

}

遇到此类问题，但看了文章还是未解决
评论或加 QQ：781378815