写在前面

这是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;
    }
}