题目描述

众所周知，小葱同学擅长计算，尤其擅长计算一个数是否是另外一个数的倍数。但小葱只擅长两个数的情况，当有很多个数之后就会比较苦恼。现在小葱给了你 $n$ 个数，希望你从这 $n$个数中找到三个数，使得这三个数的和是 $K$的倍数，且这个和最大。数据保证一定有解。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
  // 请在此输入您的代码
  int n,K;
  cin>>n>>K;
  vector<int> nums(n);
  for(int i = 0;i < n;i++){
    cin>>nums[i];
  }
  sort(nums.begin(),nums.end());
  int result = 0;
  for(int i = n-1;i>=2;i--){
    for(int j = i-1;j>=1;j--){
      for(int k = j-1;k>=0;k--){
        int sum = nums[i]+nums[j]+nums[k];
        if(sum%K==0){
          result = sum>result?sum:result;
        }
        if(sum<result){
          break;
        }
      }
      if(nums[i]+nums[j]+nums[j-1]<result){
        break;
      }
    }
    if(nums[i]+nums[i-1]+nums[i-2]<result){
      break;
    }
  }
  cout<<result<<endl;
  return 0;
}

针对这道题的数据范围特性（n≤1e5 极大，K≤1e3 极小），存在一种理论最优的算法，时间复杂度可以做到 O(n log n + K²)，这是暴力枚举无法企及的，也是蓝桥杯等竞赛中这类题目的标准解法。

这种算法的核心思想是：利用「模的分组特性」+「贪心选最大数」，彻底摆脱三重循环的束缚。因为 K 的范围很小（≤1e3），所以我们可以把「大数的枚举」转化为「小数的余数组合枚举」，再结合贪心策略保证和的最大值。

---

一、算法的核心原理（必须掌握，竞赛高频考点）

1. 模的关键性质（和之前的优化一致，但这里是算法的基石）

三个数 a, b, c 的和是 K 的倍数，当且仅当它们的余数之和是 K 的倍数，即：

(a+b+c)modK=(ra​+rb​+rc​)modK=0

其中 r_a = a % K，r_b = b % K，r_c = c % K，且 0 ≤ r_a, r_b, r_c < K。

2. 贪心策略（保证和最大的核心）

要让三个数的和最大，对于任意一种满足余数条件的组合，我们只需要从对应的余数分组中，选择最大的几个数即可。

例如：

• 若余数组合是 (r, r, r)（三个数同余），则我们需要从 r 组中选最大的 3 个数；
• 若余数组合是 (r, r, s)（两个数同余，一个不同），则我们需要从 r 组中选最大的 2 个数，从 s 组中选最大的 1 个数；
• 若余数组合是 (r, s, t)（三个数不同余），则我们需要从 r, s, t 三组中各选最大的 1 个数。

3. 分组预处理（算法的前置步骤）

1. 将原数组中的所有数，按模 K 的余数分成 K 个组，每组对应一个余数 0 ~ K-1；
2. 对每个组内的数进行降序排序，这样我们可以快速获取每组的前 1、前 2、前 3 大的数（比如 group[r][0] 是 r 组的最大值，group[r][1] 是次大值，以此类推）。

4. 枚举余数组合（算法的核心步骤）

因为 K ≤ 1e3，所以 K² ≤ 1e6，枚举所有可能的余数组合是完全可行的。我们只需要枚举所有满足 (i + j + k) % K == 0 的余数三元组 (i, j, k)，并根据组合的类型（同余情况），从对应的分组中选取最大的数，计算它们的和，最终取所有合法和的最大值即可。

为了避免重复枚举（比如 (i,j,k) 和 (j,i,k) 是同一组合），我们可以限定枚举的顺序为 i ≤ j ≤ k，这样可以将枚举的次数减少到 K²/6 左右，进一步提升效率。

---

二、算法的时间复杂度分析（为什么是最优的？）

• 分组预处理：遍历数组的时间是 O(n)，对每个组排序的时间是 O(m log m)（m 是组的大小），总排序时间是 O(n log n)（因为所有组的大小之和是 n）；
• 枚举余数组合：枚举的次数是 O(K²)，对于每个组合，计算和的时间是 O(1)；
• 总时间复杂度：O(n log n + K²)。

对于题目中的数据范围：

• n=1e5：O(n log n) ≈ 1e5 * 17 ≈ 1.7e6 次运算；
• K=1e3：O(K²) = 1e6 次运算；
• 总共约 2.7e6 次运算，远小于暴力枚举的运算量，即使是最坏情况，也能在极短的时间内完成，是理论上的最优算法。

---

三、算法的具体步骤（可直接落地）

1. 输入处理：读取 n, K 和数组 nums；
2. 分组：创建 K 个分组，将 nums 中的每个数按 num % K 放入对应的分组中；
3. 排序：对每个分组进行降序排序；
4. 预处理每组的前 3 大值：对于每个分组，我们只需要保留前 3 大的数（因为最多需要选 3 个），这样可以节省空间和时间；
5. 枚举余数组合：枚举所有 0 ≤ i ≤ j ≤ k < K，若 (i + j + k) % K == 0，则根据 i, j, k 的关系，判断是否可以从对应的分组中选出 3 个数，并计算它们的和；
6. 更新最大值：记录所有合法和的最大值，最终输出。

---

四、算法的完整代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int INF = 0x80000000; // 表示无穷小，用于处理分组中数不足的情况

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, K;
    cin >> n >> K;

    // 步骤1：创建K个分组，每组存储对应余数的数
    vector<vector<int>> groups(K);
    for (int i = 0; i < n; ++i) {
        int num;
        cin >> num;
        groups[num % K].push_back(num);
    }

    // 步骤2：对每个分组进行降序排序，并保留前3大的数（最多需要3个）
    for (auto &group : groups) {
        sort(group.rbegin(), group.rend());
        // 如果分组的大小小于3，用INF填充，方便后续处理
        while (group.size() < 3) {
            group.push_back(INF);
        }
    }

    int max_sum = INF;

    // 步骤3：枚举所有满足i ≤ j ≤ k且(i+j+k)%K == 0的余数组合
    for (int i = 0; i < K; ++i) {
        for (int j = i; j < K; ++j) {
            for (int k = j; k < K; ++k) {
                if ((i + j + k) % K != 0) {
                    continue;
                }

                // 步骤4：根据i, j, k的关系，选取对应的数，计算和
                int current_sum = 0;
                if (i == j && j == k) {
                    // 情况1：三个数同余，需要从i组选前3大的数
                    current_sum = groups[i][0] + groups[i][1] + groups[i][2];
                } else if (i == j && j != k) {
                    // 情况2：前两个数同余，第三个数不同，需要从i组选前2大的数，k组选前1大的数
                    current_sum = groups[i][0] + groups[i][1] + groups[k][0];
                } else if (i != j && j == k) {
                    // 情况3：后两个数同余，第一个数不同，需要从i组选前1大的数，j组选前2大的数
                    current_sum = groups[i][0] + groups[j][0] + groups[j][1];
                } else {
                    // 情况4：三个数不同余，每组选前1大的数
                    current_sum = groups[i][0] + groups[j][0] + groups[k][0];
                }

                // 步骤5：更新最大值
                if (current_sum > max_sum) {
                    max_sum = current_sum;
                }
            }
        }
    }

    // 输出结果
    cout << max_sum << endl;

    return 0;
}

五、两种算法的对比

算法	时间复杂度	空间复杂度	适用场景	竞赛优先级
你的暴力枚举 + 剪枝	O (n³)（带剪枝）	O(n)	小数据范围（n≤1e3）	低
模分组 + 贪心枚举	O(n log n + K²)	O(n)	大数据范围（n≤1e5）	高

关键提示：

1. 你的暴力枚举 + 剪枝，只适用于小数据范围，如果题目中的 n 稍微大一点（比如 n=1e4），就会超时；而模分组 + 贪心枚举，适用于所有数据范围，尤其是题目中的大数据范围，是竞赛中的标准解法。
2. 这种算法的核心思想是利用小范围的参数（这里是 K）来降低时间复杂度，这是竞赛中处理大数据范围问题的常用技巧，比如：
   • 当题目中出现 K≤1e3 或 K≤1e4，而 n≤1e5 或 n≤1e6 时，大概率可以用这种「分组 + 枚举小范围参数」的方法来解决。
3. 对于这道题，模分组 + 贪心枚举的算法不仅效率更高，而且能保证找到全局最大值，不会受到极端数据的影响，是更优的选择。