携程算法岗笔试【20230525】

前两天写了携程的一道笔试题，感觉题目质量挺不错，这里记录一下。

1. 题目

题目大意如下：
现有n套试卷，每套试卷包含的题目数是i。游游每天的早上和下午都可以选择做一套试卷，当然也可以选择摸鱼（不做题），但是必须满足游游每天做的题目是k的整数倍。求游游最多可以做几天的题？
输入：第一行是n,k；第二行是每套试卷的题数组成的一个数组。
输出：游游最多可以做多少天的题？
样例输入：

5 3 
1 2 3 4 5
1
2

样例输出：3
样例解析：

• 第一天上午做1题，下午做5套题
• 第二天上午做2题，下午做4题
• 第三天上午做3题，下午摸鱼
  总共可以做三天。

2.分析

其实这题难在：如何匹配？比如说你怎么知道1要和5搭配，而2就和4搭配？因此暴力的方法行不通。于是尝试考虑使用动态规划的方法。这题用dp来解就非常巧妙。
我们令dp[i] 表示第i套卷可以得到的最大天数。 这个令的过程是dp的精华，当然这也不是我一个人想出来的，小师妹跟我一起思考这个问题，然后我就想出来了。
得到假设之后，就需要考虑怎么得到递推式了，即dp[i] 与 dp[i-1]的关系。 其实主要分成两部分：

• 如果第i天的作业量刚好是k的倍数，那么直接在 dp[i-1]的基础上+1，
• 如果第天的作业量不是k的倍数，那么就需要判断前面是否有剩余的作业题可以和当前补成k的倍数，如果能补，那么就是 dp[i] = dp[i-1] + 1， 如果不能补，那么就是dp[i] = dp[i-1]

3. 代码

上面这个思想的代码能直接AC笔试题，这里不再给出了。