首页 > 试题广场 >

天弃之子

[编程题]天弃之子
  • 热度指数：1980 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
有一款游戏，过关的方式是按按钮。
游戏一共有关，每一关有个按钮，其中只有唯一一个按钮是可以通关的，按下其他的按钮游戏就会失败。
好在这个游戏可以重来，而且由于设计者的疏忽，每一关的通关按钮是不变的，所以你可以记住前几关的按钮，重来时就可以直接通关。
但是...你的运气似乎用在了其他地方，你使用了最多的按按钮次数才成功通关。
求这个最多的按按钮次数吧！

本题为核心代码模式，代码框中预设代码已经指定好类名、方法名、参数名，请勿修改或重新命名，直接返回值即可。
示例1

输入

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

输出

49
示例2

输入

[2,2,2]

输出

9

说明

第一关消耗两次得到通关按钮后直接进入第二关，经历一次失败后重新来到第二关得到通关按钮进入第三关，再失败一次后直接通关，消耗次数为1+2+3+3=9

备注:
输入一维数组，表示每一关的按钮数


算法知识视频讲解
添加回答
牛客135116964号头像 牛客135116964号
从最后一个开始，计算每一关按按钮的次数，最后加起来就好了，java 执行时间227ms 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param buttons int整型一维数组 
     * @return long长整型
     */
    public long findMaxButtons (int[] buttons) {
        int len = buttons.length;
        long sum = 0;
        long pre = 1;
        for(int i = len-1;i>=0;i--){
            pre = pre + buttons[i] - 1;
            sum += pre;
        }
        return sum;
    }
}


发表于 2022-02-04 01:21:34 回复(0)
mysteriousTime头像 mysteriousTime

importjava.util.*;

publicclassSolution { 

publiclongfindMaxButtons (int[] buttons) {

    Long max = 0L;

    for(inti = 0;i<buttons.length;i++){

        int a = buttons[i];

       max + =(a-1)*(i+1);

    }

    return max + buttons.length;

}

}

我这答案为啥是错的，哪位大神解答一下哦

编辑于 2022-01-29 15:06:44 回复(3)
山海意明头像 山海意明 
long long findMaxButtons(vector<int>& buttons) {
    long long sum = 0;
    for (long long i = 0; i < buttons.size(); i++) {
        sum += ((i + 1) * (buttons[i] - 1LL) + 1LL);
    }
    return sum;
}
公式就  sum += ((i + 1) * (buttons[i] - 1LL) + 1LL); 这一条，自己画图推。
发表于 2021-08-02 15:54:55 回复(0)
pein531头像 pein531
来到第关时，前关的按钮已经记住了，但在本关会失败次，本关每失败一次，前面的关还需要重新走一遍（能来到本关，说明前面关卡的通关按钮已经记住，可以一遍速通）。因此来到本关后要试出本关的通关按钮需要次，可以得到递推计算公式，注意最后还要加上一遍速通消耗的按钮数。 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param buttons int整型一维数组 
     * @return long长整型
     */
    public long findMaxButtons (int[] buttons) {
        // write code here
        long res = buttons.length;
        for(int i = 0; i < buttons.length; i++){
            res += (long)(buttons[i] - 1) * (i + 1);
        }
        return res;
    }
}
代码实现时注意下标与次数之间的变换关系
编辑于 2022-02-23 13:30:22 回复(2)
敖星星头像 敖星星
通过每一层所需要的按钮数分为三部分  试错次数   赶路成本  成功次数

(0层开始)第i层的所需次数=试错（buttons[i]-1）+ 成功(1) + 赶路(buttons[i-1]*i) 

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param buttons int整型vector 
     * @return long长整型
     */
    long long findMaxButtons(vector<int>& buttons) {
        // write code hee
        long long sum=0;
        for(int i=0;i<buttons.size();i++)
        {
            sum +=buttons[i];
            sum+=(buttons[i]-1)*i;
        }
        return sum;
    }
};


发表于 2022-07-16 01:27:41 回复(0)
leesurelye头像 leesurelye
模拟 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param buttons int整型一维数组 
# @return long长整型
#
class Solution:
    def findMaxButtons(self , buttons ):
        # write code here
        n = len(buttons)
        ans = 0
        for i in range(n):
            if buttons[i] == 1:
                continue
            else:
                ans += (buttons[i]-1) * (i + 1)
                buttons[i] = 0
        return ans + n


发表于 2022-07-13 15:16:37 回复(0)
牛客589531283号头像 牛客589531283号
 publiclongfindMaxButtons (int[] buttons) {
        // write code here
        long num = 0;
        for(int i = 0; i < buttons.length; i ++) {
            if(i == buttons.length - 1) {
                num += buttons[i] * (i + 1);
            } else{
                if(buttons[i] > 1) {
                    num += (buttons[i] - 1) * (i + 1);
                }
            }
 
        }
        return num;
    }
我这样写 为啥是错的 有没有大神解答一下 谢谢
发表于 2022-06-22 22:53:57 回复(0)
牛客449472943号头像 牛客449472943号
大佬们，可以看看我的代码错哪里了吗 
import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param buttons int整型一维数组
     * @return long长整型
     */
    public long findMaxButtons (int[] buttons) {
        // write code here
        long count = 0;
        for (int i = 0; i < buttons.length; i++) {
            if (buttons[i] == 1) {
                count++;
            } else {
                long tmp = (buttons[i]-1)*i+buttons[i];
                count+=tmp;
            }
        }
        return count;
    }
}

编辑于 2022-04-14 21:08:06 回复(0)
回家找个班上吧头像 回家找个班上吧
以[2,2,2]为例。
想要知道第0关的过关按钮，最多需要按(0+1)*(2-1)次按钮，此时已经知道了第0关的过关按钮;
想要知道第1关的过关按钮，最多需要按(1+1)*(2-1)次按钮，此时已经知道了第1关的过关按钮;
想要知道第2关的过关按钮，最多需要按(2+1)*(2-1)次按钮，此时已经知道了第2关的过关按钮;
现在知道了所有关卡的过关按钮，那么再来一遍速通，需要按3次(数组的大小)按钮。
更一般化，要想知道第i关(从0开始计数)的过关按钮，最多需要按(i+1)*(buttons[i]-1)次按钮；
整个过程就是不断累加的过程，直到知道了所有关卡的过关按钮。
最后，需要进行一次"速通"，即加上数组大小。 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param buttons int整型vector 
     * @return long长整型
     */
    long long findMaxButtons(vector<int>& buttons) {
        // write code here
        // 要知道第i(从下标0开始)关的过关按钮，最多需要按(i+1)*(a[i]-1)次按钮
        long long res = 0;
        for (int i = 0; i < buttons.size(); ++i) {
            res += (long long)(i + 1) * (buttons[i] - 1);
        }
        res += buttons.size();  // 最后加上一遍速通
        return res;
    }
};


发表于 2022-04-07 22:10:52 回复(0)
想吃饼饼头像 想吃饼饼
这道题更像是一道数学题，通过题意我们可以知道，在每一次进入下一关之前都需要在该关按错a[i]-1个按钮，在这一次之后我们就按对按钮，进入下一关的迭代，到达每一关我们一共需要按下i次，即通过前i-1关，加上在第i关的1次，单轮我们在第i关需要按下i+1次，为了得到正确的结果，我们需要在第i关按下（i+1）*（a[i]-1)次，最后，我们得到了一条完全正确的路径，需要再在前序结果的基础上再走一次，即在原结果上+i，即得到结果 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param buttons int整型vector
     * @return long长整型
     */
    long long findMaxButtons(vector<int>& buttons) {
        // write code here
        long long ans=0;
        long long len = buttons.size();
        for(long long i=0; i<len; i++){
            ans +=((i+1)*(buttons[i]-1));
        }
        ans += len;
        return ans;
    }
};
发表于 2022-03-30 22:02:09 回复(0)
wonderson头像 wonderson
太草了，难怪过不了，返回值类型写错了，十有***越界了。 
import java.util.*;
public class Solution {
    public long findMaxButtons (int[] buttons) {
        int n = buttons.length;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (buttons[i] == 0) {
                return 0;
            }
            sum += (i + 1) * (buttons[i] - 1);
        }
        sum += n;
        return sum;
    }
}

发表于 2022-03-23 23:47:07 回复(0)
小蓝1l头像 小蓝1l 
function findMaxButtons( buttons ) {
    let res=0
    let add=0
    for(let i=0;i<buttons.length;i++){
        add++
        if(buttons[i] === 1){
            continue
        }else{
            if(i<buttons.length-1){
            res+=add*(buttons[i]-1)
            }else{
                res+=add*buttons[i]
            }
        }
    }
    return res
}
module.exports = {
    findMaxButtons : findMaxButtons
};

发表于 2022-03-09 02:13:51 回复(0)
C/C++
牛客535805470号头像 牛客535805470号 
class Solution {
public:
    long long findMaxButtons(vector<int>& buttons) {
        int n = buttons.size();
        long long sum = 0;
        for (int i=0;i<n;i++)
        {
            sum +=(i+1)*(buttons[i]-1LL)+1LL;
            //一定要把所有类型转化为long long

            //下面这个是错的，因为乘法里面算出来是整型，
            //sum +=(i+1)*(buttons[i]-1)+1LL;
        };
        return sum;
    }
};

发表于 2022-02-24 22:15:28 回复(0)
int0832577头像 int0832577 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param buttons int整型vector 
     * @return long长整型
     */
    long long findMaxButtons(vector<int>& a) {
        // write code here
        long long ans=0;
        int n=a.size();
        ans+=a[0];
        for(int i=1;i<n;i++){
            ans+=a[i]+(a[i]-1)*i;
        }
        return ans;
    }
};
简单计数题

编辑于 2021-12-22 21:22:59 回复(2)
牛客995323969号头像 牛客995323969号
样例是114514也太草了😂
发表于 2021-10-20 13:29:19 回复(1)
TuLoo头像 TuLoo 
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param buttons int整型一维数组 
 * @return long长整型
 */
function findMaxButtons( buttons ) {
    // write code here
    let counted = 0;
    let dp=[];
    dp[0] = 0;
    for(let i=0;i<buttons.length;i++){
       if(i===0){
           dp[i] = buttons[i];
       }
        else{
            dp[i] = dp[i-1]+i*(buttons[i]-1)+buttons[i]
        }
    }
    return dp[buttons.length-1]
}
module.exports = {
    findMaxButtons : findMaxButtons
};

发表于 2021-09-15 10:01:23 回复(0)
玄成头像 玄成
思路前面大牛们都有了，有个坑就是遍历的时候，int i会让运算都是int，哪怕dp数组是longlong也不行，所以得long long i，靠
发表于 2021-08-22 16:57:57 回复(0)
WeiC0der头像 WeiC0der 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param buttons int整型vector 
     * @return long长整型
     */
    long long findMaxButtons(vector<int>& buttons) {
        // write code here
        long long ret = 0;                        //最后总共需要按键次数
        for(int i = 0; i < buttons.size(); ++i){
            //buttons[i] - 1 代表在第 (i+1) 关时，我们把所有非正确按键都试了
            //(i + 1) 代表试错时我们需要从第 1 关没关按键 1 次，直到第 (i + 1) 关
            //最后，加上 1 表明我们按下第 (i + 1) 关的正确按键
            //至此，我们通过第 (i+1) 关需要按键次数
            //我们一共需要通过 buttons.size() 个关，只需要把每关按键次数相加即可
            ret += (i + 1) * (buttons[i] - 1LL) + 1LL;
        }
        return ret;
    }
};
题目要求：我们一直是以最差运气进行按键，即我们需要先把每一关的非通关按键按完以后，这才能通过本关；同时，我们只有通过前一关，才能去尝试下一关，直至我们通过最后一个关；把通过每一关的按键次数相加，即是最后的答案。
发表于 2021-08-09 20:35:37 回复(0)
一大岐头像 一大岐 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param buttons int整型一维数组 
     * @return long长整型
     */
    public long findMaxButtons (int[] buttons) {
        // write code here
        int size = buttons.length;
        long total = 0;
        for(int i = 0; i < size; i++){
            // 第i关需要按的次数 = 前i-1关需要按从次数 
            //                 + 第i关需要按的次数buttons[i]
            //                 + 第i关前（buttons[i]-1）失败时，前i-1关需要增加的次数
            total += buttons[i] + (buttons[i] - 1L) * i;
        }
        return total;
    }
}
发表于 2021-08-03 15:15:40 回复(0)
C/C++
头文字F头像 头文字F
看到long long的时候一定要注意显式的类型转换，不然会出现int越界
递归方式容易理解，但容易导致栈溢出： 
long long findMaxButtons(vector<int>& buttons){
    if(1 == buttons.size()){
        return buttons[0];
    }else{
        long long numSuccess = findMaxButtons(vector<int>(buttons.begin(), buttons.end()-1)) + 1;
        long long numFail = (long long)buttons.size() * (buttons[buttons.size() - 1] - 1);
        return  numSuccess + numFail;
    }
}
动态规划的非递归方式： 
    long long findMaxButtons(vector<int>& buttons) {
        if(0 == buttons.size()) return 0;
        long long curSum = buttons[0];
        for (int i = 1; i < buttons.size(); i++)
        {
            long long numSuccess = curSum + 1;
            long long numFail = (long long)(i + 1) * (buttons[i] - 1);
            curSum = numSuccess + numFail;
            //curSum = curSum + 1 + (i + 1) * ((long long)buttons[i] - 1);
        }
        return curSum;
    }




编辑于 2021-07-30 17:26:11 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试开发工程师 测试工程师 2021 牛客 Java工程师
来自：【2021】牛客模考C...
上传者：小小
难度：
25条回答 3050浏览

热门推荐

通过挑战的用户

相关试题

天弃之子

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号