滴滴0904 笔试 伪题解

第一题 动态规划

原题

小明有n天假期，有无数页作业题，每天做题[1, m]道，
且第二天做的题不少于第一天做的题。
妈妈有k条奖励计划，
一条奖励计划是这样的四元组{x,y,a,b}，如果x天比y天多做a道题，那么奖励b。
求小明可以获得的最大奖励。
数据范围：
    天数n:[1,10] 
    每天做题m:[1,10]
    奖励计划数量k:[1,10] 
    天 y>x且在n范围内 多做a:[0,m] 奖励b:[1,1000]

输入：
n,m,k 接下来是k行四元组{x,y,a,b}

样例：
4 4 4
1 2 3 6
2 3 1 3
3 4 2 4
3 4 2 1
输出：8
解释：小明在4天内每天做这么多题:[1,1,2,4]，可以获得最多奖励

思路
第一眼没什么思路，考虑暴力枚举，那么粗略估计一下需要循环最多n^m * m次，也就是最高100亿次，AC不太行。
第二眼感觉像背包问题，后来发现就是一普通动态规划，背包问题的变种。
考虑暴力法中，每个天的最大值不存储，存储一下，就可以动态规划了。

首先考虑如何存储奖励四元组，因为显然每次都要找到第一天和最后一天，所以考虑使用map<array[2], array[2]>，但是第一天和最后一天可能是一样的而作业差值不一样，与其用array[2]找到后判断不如直接定义为map<array[2], int> ，这样既可以找到同天数不同差值的情况，也能考虑到重合问题（如样例情况所示）。

然后考虑如何使用dp。

1. 考虑dp含义，可以按照最原始的背包问题设置二维数组dp=int[i][j]，dp[ i ][ j ]表示第i天做了j道题获得的奖励，这里不是最大奖励哦，因为不知道后面是不是有更大的奖励。
2. 考虑递推公式，

   if 从map中找到了对应的开始和结束天数和差值：
    对于作业量从1到每天最大的作业量：
        dp[结束天][作业量+差值] = dp[开始天][作业量] + 结束天奖励

3. 考虑遍历顺序：开始天和结束天有两个，外层2个循环。每天最多m个作业量，再加一个循环，内部对于结束天和开始天 差值对应的结束天每一项作业都要赋值，再加一个循环。

对于结束天和开始天 差值对应的结束天每一项作业都要赋值,这句话什么意思呢

假如 开始天1 的奖励是这样的[11, 22, 33, 44, 55] 差值是2
那么 结束天n 的奖励是是怎样算的呢
作业数：    1   2   3     4     5
开始天奖励：11, 22, 33,   44,   55
            \    \    \
              \    \     \  
                \    \     \ 
                    \   \    \
结束天奖励：0,  0,  11+2, 22+2, 33+2

对每一个开始天和结束天都进行这样的赋值就好了。
4. 考虑dp数组初始化：没什么好初始化的，全部为0就好了。

接下来用伪代码的方式展示思路

输入n,m,k
定义task=map<int[3],int>
定义res=0
k次循环
    task[{x, y, a}] = task[{x, y, a}] + b

for 开始天=1; 开始天<=最大天; 开始天++
    for 结束天=开始天+1; 结束天<=最大天; 结束天++
        for 差值=0; 差值<=每天最大作业; 差值++
            if task[{开始天, 结束天, 差值}]存在
                结束天奖励 = task[{开始天, 结束天, 差值}]
                for 开始天作业量=1; 开始天作业量+差值<=每天最大作业; 开始天作业量
                    dp[结束天][开始天作业量+差值]= 结束天奖励 + dp[开始天][开始天作业量]
                    res=max(res, dp[结束天][开始天作业量+差值])
                endfor
            endif
        endfor
    endfor
endfor

输出res

这样大概最多循环10 * 10 * 10=1000次，还是可以接受的。
可运行代码：没来得及提交不知道是否AC。
golang代码

package main

import "fmt"

func main() {
    //n天数 m页数
    var n, m, k int
    fmt.Scan(&n, &m, &k)
    task := make(map[[3]int]int)
    var x, y, c, r int
    for i := 0; i < k; i++ {
        fmt.Scan(&x, &y, &c, &r)
        task[[3]int{x, y, c}] += r
    }

    //dp[i][j]表示第i天，作业量为j的最大收益
    //dp[i][j]
    var maxRes int
    dp := make([][]int, n+1)
    for i := 0; i < len(dp); i++ {
        dp[i] = make([]int, m+1)
    }
    for i := 1; i <= n; i++ {
        for j := i + 1; j <= n; j++ {
            for p := 0; p <= k; p++ {
                if v, ok := task[[3]int{i, j, p}]; ok {
                    for tp := 1; tp+p <= k; tp++ {
                        dp[j][tp+p] = v + dp[i][tp]
                        maxRes = max(maxRes, dp[j][tp+p])
                    }
                }
            }
        }
    }

    fmt.Println(maxRes)
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

/**

4 4 4
1 2 3 6
2 3 1 3
3 4 2 4
3 4 2 1


8
*/

第二题

原题

输入n个数，从中取出一些数，让他们的平均值不大于最大值的k倍，即满足avg*k <= maxValue，求最多可以取多少个数
输入：n k
接下来n个数

样例：
输入
5 2
1 15 2 4 3
输出 4
解释 若取1 2 3 4 10, avg=(1+2+3+4+5+15)/5=6 最大值15 > 6*2，不可行
若取1 2 3 4 avg=(1+2+3+4)/4=2.5 最大值4 < 2.5*2

思路 只过了82% 有没有大佬看看我思路出错在哪里

1. 对输入数排序
2. 从大数到小数遍历，当遇到大数大于平均值的k倍时停止遍历，此时数组下标+1就是最多的数量了
   伪代码

   k = 输入的倍数系数
   nums = 输入并排序
   sum = nums求和
   for i=nums[nums.size - 1]; i>=0; i--
    if nums[i] > sum/(i+1)*k
        break
    sum = sum-nums[i]
   打印i+1