牛客网

2024-07-13 15:08| 来源: 网络整理| 查看: 265

题目

有一款游戏，过关的方式是按按钮。游戏一共有n关，每一关有a[i]个按钮，其中只有唯一一个按钮是可以通关的，按下其他的按钮游戏就会失败。好在这个游戏可以重来，而且由于设计者的疏忽，每一关的通关按钮是不变的，所以你可以记住前几关的按钮，重来时就可以直接通关。但是...你的运气似乎用在了其他地方，你使用了最多的按按钮次数才成功通关。求这个最多的按按钮次数吧！

备注

输入一维数组a[i],表示每一关的按钮数 1 ≤ a[i] ≤ 10^5 1 ≤ a[i] 数组的长度 ≤ 10^5

输入

[1,1,4,5,1,4]

输出

思路假设最理想的情况下一次就能顺利过关即没关只需按一次，则按按钮次数为数组的长度（a.length）去掉正确的按钮，则每关要失败a[i]-1次可转换为每关失败次数[0,0,3,4,0,3] 每次执行都需要先执行前 i-1 关例如：第三关要执行3次失败，每次都要先执行前两关，再执行第三关即每次都要按 i 次按钮，共（a[i]-1）* i 次题解 public long findMaxButtons (int[] a) { long res = a.length; for(int i = 0; i < a.length; i ++) { // 第i关要失败a[i] - 1次，每次都要按i次按钮，共(a[i] - 1) * i次 // i表示第几关，i从0开始，故+1 res += (long)(a[i] - 1) * (i + 1); } return res; } 复杂度分析时间复杂度：O(N) 空间复杂度：O(1)

【本文地址】

牛客网

牛客网

今日新闻

推荐新闻