首页 > 5月9日 美团春招后端开发实习生 笔试第三题复盘[贪心法]
头像
al-viewer
发布于 2021-05-09 19:52
+ 关注

5月9日 美团春招后端开发实习生 笔试第三题复盘[贪心法]

写在前面

这是2021年5月9日,美团春招最后一场笔试“后端开发”实习的题目,4 + 1道编程,至于为什么只写这一道,是因为前两道忘了,后面因为太菜还没来得及看,而这道题卡了我一个小时也没有做出来

第三题

题目描述

小明练琴,他有一个初始状态值x,每天他可以选择练琴或者休息,如果练琴的话会收获经验值x,然后消耗状态值a,如果某休息的话会增加经验值b,一共n天时间,问小明在时间内最多收获多少经验值?
1 <= x, a, b, n <= 10^6

输入顺序为x a b n
官方例子:[10 5 5 3] 结果为25
第一天休息 状态值15 收获0
第二天练琴 状态值10 收获15
第三题练琴 状态值5 收获25

思路复盘

一开始看到这种题想到的肯定是动态规划,而且动态规划肯定是可以做出来的(是否超时就不知道了),但当时觉得动态规划好像有点麻烦,灵光一现,觉得贪心算法似乎可以解决,我之前一直休息,然后把状态值拉高,最后连续练琴就能取到最优解。试了几个没有找到反例,就按照这个思路求解了。
然后就掉坑里出不来了结果一直是通过18%(只过了示例那个解)

错误查找

笔试结束后一直怀疑思路错了,以为贪心是无法求解的,但是在牛客上看到了别人有用贪心法AC的,于是问大佬要了代码,开始分析自己的问题。

问题查找:一开始的求休息天数公式就错了
虽然都是贪心算法,之前一直休息,然后一直训练
但我想的是,休息到最后一天的时候状态值降为零是最优情况,所以求休息天数i的公式时设置的是:

x + b * i = a * (n - i) 推出

i = (a * n - x) / (b)

但是这并不是最优值,而是该用等差求和的公式通过求导找到最大值点

f(i) =[ (x + b * i) + (x + b * i - a * ( n - i - 1)]* (n - i )/ 2

求导后可以得出

i = (2 * b* n +2 * a * n-2 * x - a ) / ( 4 * b + 2 * a )

过程:
图片说明

但是i不一定是整数(且向下取整),所以还需要计算i + 1时候的情况,取最大值

Java代码 及 结果

import java.util.Scanner;

public class Test2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNextInt()) {
            int dataNum = scan.nextInt();
            for(int i = 0; i < dataNum; i++) {
                long x = scan.nextLong();
                long a = scan.nextLong();
                long b = scan.nextLong();
                long n = scan.nextLong();
                solution2(x, a, b, n);
            }
        }
    }

    public static void solution2(long x, long a, long b, long n) {
        long relaxTime = (2*b*n+2*a*n-2*x-a)/(4*b+2*a);//求和公式的极值点横坐标,可见上面的推导过程
        long result = 0;
        result = Math.max(result, sum(relaxTime, x, a,b,n));
        result = Math.max(result, sum(relaxTime + 1, x, a,b,n));

        System.out.println(result);
    }

    public static long sum(long relaxTime, long x, long a, long b, long n) {
        return (n - relaxTime) * (x + b * relaxTime + x + b * relaxTime - a * (n - 1 - relaxTime)) / 2;
    }
}

图片说明

全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐