🎯美团笔试-空间回廊

⭐ 孟应杰的网站: 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号房间再留下一个烙印.

⌨代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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