PDD服务端实习 - 笔试

2025年3月9日 10：00-12：00

四道编程题100分（每道题25分）：

多多的传送门：

在 x = 0 的位置，每次可以从数组中选择一个数字进行传送，传送到 x = x + a 的位置，数组中的数字有正数或负数。

多多有一次“反转能力”，使自己的位置从 x = t 传送到 x = -t 的位置，每次传送可以使用一次（或不使用）。

问多多能传送到的最远位置距离x = 0是多少？

输入：int[]

输出：能达到的最远位置

例如：
输入：[1,-3,4,2,-1]
输出：11多多先选择-3，-1传送到-4位置使用反转能力到4，再选择1，4，2到达位置11

多多的传送门2：

在 x = 0 的位置，每次可以从数组中选择一个数字进行传送，但必须依次选择输入数组中的数字。

多多有一次“反转能力”，使自己的位置从x = t 传送到 x = -t 的位置，问多多能传送到的最远位置距离x = 0是多少？

输入：int[]

输出：能达到的最远位置

例如：
输入：[1,-4,10,-30,2]
输出：37多多先选择1，-4，10传送到7位置使用反转能力到-7，再选择-30到达最远位置-37

多多爱读书：

每次能读一页书，读一页书需要1分钟，能汲取当页书的所有知识量。

多多有一个能力，每分钟能读2页书，但汲取的知识量是两页书知识量总和的一半。

问给定一个书的页数和时间，多多在该时间内最多能汲取多少知识量，如果不能读完书返回-1。

输入：int[] 代表每页书的知识量，int 总时间

输出：double 规定时间能读完书能汲取的最大知识量

例如：
输入：[1,2,3,2,1]  3
输出：6.0多多第1分钟读2页书，获得知识量1.5，第2分钟读1页书，获得知识量3，第3分钟读2页书，获得知识量1.5，共6.0

座位安排：

一共n行m列座位，给一群身高各不相同的客人分配座位，保证身高的坐在后面，身高矮的坐在前面。

设身高为 hi<hj ，则其座位索引 si<sj 。

客人会顺序到场，坐在右边的客人路过左边的座位时如果有客人落座，那么会感到拥挤，每路过一个落座的客人拥挤程度 +1 。

问如何分配座位使得拥挤程度最小？

输入：int 多少行座位，int 多少列座位，int[] 代表客人到达的先后顺序

输出：最小的拥挤度

例如：
输入：3 3 [3,2,1,1,1,1,1,4,5]
输出：3第一个身高为3的客人坐在(3,1)(第三行第一列)，第二个身高为2的客人坐在(2,3)，第三到第七个身高为1的客人坐在第一排和第二排的空位，第八个身高为4的客人坐在(3,2)，路过身高3的客人，拥挤度+1，第九个身高为5的客人坐在(3,3)，路过身高3、4的客人，拥挤度+2