小米2025年校招笔试真题手撕（二）

一、题目

给一个长度为n的序列和一个整数x，每次操作可以选择序列中的一个元素，将其从序列中删去，或者将其值加一。

问至少操作多少次，可以使操作后的序列（可以为空）中数字之和是x的倍数。

输入描述：

第一行两个用空格隔开的正整数n和x，含义如问题描述中所述。

第二行是n个用空格隔开的正整数A[1],A[2],…,A[n]，表示序列中n个元素的值。

n ≤ 1000，x ≤ 1000，A ≤ 1000

输出描述：一行一个整数，表示使序列中数字之和是x的倍数所需要的最少操作数。

样例输入1：

1 3

4

样例输出：

1

解释：直接将序列中唯一的元素删去即可。

输入样例2：

3 5

1 3 3

输出：

2

解释：可能的一种操作为，删去最后一个元素，再使第一个元素加一，得到的序列为2 3。

二、分析

该问题要求我们找到最少的操作次数，使得经过若干次删除元素或加一操作后，序列的数字之和是给定整数x的倍数。操作包括删除一个元素或给一个元素加一，每次操作算一次。我们的目标是找到一个策略，通过这两种操作的组合，使得总和成为x的倍数，并且操作次数最少。

首先，我们需要理解问题的目标是让总和 S 满足 S ≡ 0 mod x。初始时，序列的总和为 sum。如果 sum 已经是x的倍数，那么不需要任何操作，直接返回0。否则，我们需要通过删除元素或增加元素的值来调整总和，使其成为x的倍数。

删除元素会减少总和，而加一则会增加总和。我们需要在这两种操作之间找到平衡，使得总和调整到最近的x的倍数，并且操作次数最少。

可能的策略包括：

1. **计算当前总和对x的余数**：计算初始总和 sum 对x取余得到 r。如果 r == 0，直接返回0。否则，我们需要调整总和，使其增加或减少一定的量，使得新的总和对x取余为0。

2. **考虑加一操作**：假设我们不删除任何元素，那么可以通过给某些元素加一来增加总和。需要增加的总和量为 (x - r) mod x。对于每个元素，我们可以计算将其增加到足够次数所需的操作数，使得总和增加 (x - r)。这可能适用于当总和接近x的下一个倍数时。

3. **考虑删除元素**：删除元素会减少总和。对于每个元素，我们可以计算删除它之后的新总和，并检查是否满足条件。此外，可能需要结合删除多个元素的情况。

4. **尝试所有可能的组合**：对于较小的n和x，可以尝试所有可能的删除和加一的组合，找到操作次数最少的方案。但这种方法在n较大时效率较低。

5. **动态规划**：可以考虑动态规划的方法，记录达到某个余数所需的最小操作次数。例如，我们可以维护一个数组 dp，其中 dp[i] 表示达到余数i所需的最小操作次数。初始时，dp[sum % x] = 0。然后，对于每个元素，我们可以更新 dp 数组，考虑加一或删除该元素后的效果。

在实现时，我们需要综合考虑上述策略，并选择最适合问题规模的方法。对于题目给定的约束条件（n ≤ 1000，x ≤ 1000，A ≤ 1000），动态规划可能是一个可行的选择。

以样例输入1为例：

输入：
1 3
4

初始总和是4，4 mod 3 = 1。我们需要调整总和到3的倍数。可以选择删除唯一的元素，操作次数为1，或者给该元素加2次达到6（3的倍数），操作次数为2。因此，最少操作次数是1。

样例输入2：

输入：
3 5
1 3 3

初始总和是7，7 mod 5 = 2。我们需要调整总和到5的倍数。可能的策略是删除最后一个3（总和变为4），然后给第一个元素加1（总和变为5，操作次数2）。或者有其他组合，但最少操作次数是2。

在代码实现中，我们需要遍历所有可能的操作组合，并找到操作次数最少的方案。这可能需要尝试所有可能的删除元素的子集，并计算对应的加一操作次数，或者使用动态规划来记录最小操作次数。

三、代码

说起来你们可能不信，这段代码是军哥给我的

n, x = map(int, input().split())
a = list(map(int, input().split()))sum_a = sum(a)
remainder = sum_a % xif remainder == 0:print(0)
else:dp = [float('inf')] * xdp[remainder] = 0for num in a:new_dp = dp.copy()for i in range(x):if dp[i] != float('inf'):# 删除当前元素new_remainder = i - (num % x)if new_remainder < 0:new_remainder += xnew_dp[new_remainder] = min(new_dp[new_remainder], dp[i] + 1)# 不删除当前元素new_remainder_add = (i + num) % xnew_dp[new_remainder_add] = min(new_dp[new_remainder_add], dp[i])dp = new_dpmin_operations = min(dp[0], len(a))  # 最坏情况下删除所有元素print(min_operations)

这段代码首先计算初始总和对x的余数。然后使用动态规划的方法来记录达到每个可能的余数所需的最小操作次数。对于每个元素，考虑两种情况：删除该元素或不删除该元素，更新动态规划数组。最后，取达到余数0所需的最小操作次数，或者删除所有元素的操作次数（作为最坏情况）。