美团笔试——空间回廊(c++)

⭐ 孟应杰的网站: www.mengyingjie.com ⭐

🎯空间回廊

📌题目描述:

有一款叫做空间回廊的游戏,游戏中有着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

发表评论

电子邮件地址不会被公开。 必填项已用*标注