蓝桥杯 20. 倍数问题
倍数问题
原题目链接
题目描述
众所周知，小葱同学擅长计算，尤其擅长判断一个数是否是另一个数的倍数。但当面对多个数时，他就比较苦恼了。
现在小葱给了你 n 个数，希望你从中找出三个数，使得这三个数的 和是 K 的倍数，并且这个 和最大。
题目保证一定存在解。
输入描述
- 第一行包含两个正整数
n和K。 - 第二行包含
n个正整数，代表给定的数列。
数据范围：
- 1 ≤ n ≤ 10⁵
- 1 ≤ K ≤ 10³
- 所有给定的整数不超过 10⁸
输出描述
输出一行一个整数，表示满足条件的最大和。
输入示例
4 3
1 2 3 4
输出示例
9
c++代码
#include<bits/stdc++.h>using namespace std;typedef long long ll;int main() {ll n, K, x, a, b, c, ans = 0;cin >> n >> K;vector<vector<ll>> arr(K);for (ll i = 0; i < n; i++) cin >> x, arr[x % K].push_back(x);for (ll i = 0; i < K; i++) sort(arr[i].begin(), arr[i].end());for (ll i = 0; i < K; i++) {if (arr[i].size() <= 0) continue;a = arr[i].back(), arr[i].pop_back();for (ll j = i; j < K; j++) {if (arr[j].size() <= 0) continue;b = arr[j].back(), arr[j].pop_back();ll val = K - i - j;while(val < 0) val += K;while(val <= K - 1) {if (arr[val].size() > 0) c = arr[val].back(), ans = max(ans, a + b + c);val += K;}arr[j].push_back(b);}arr[i].push_back(a);}cout << ans;return 0;
}//by wqs
题目解析
给你 n 个数和一个整数 K，从这 n 个数中选出三个数 a, b, c，要求：
(a + b + c) % K == 0a + b + c最大化
假设(a + b + c) % K = 0，
那么(a % K + b % K + c % K) % K = 0，
假设a % K = d， b % K = e，
根据(d+ e + c % K) % K = 0，并且数据的值都是正数
也就是说d + e + c % K = n * K(n >= 1)，
也就是说c % K = n * K - d - e
那么c % K = K - d - e 或者 2 * K - d - e或者3 * K - d - e…
不要认为有很多种情况，我们看看c % K的范围，
显然，0 <= c % K <= K - 1，
也就是0 <= n * K - d - e <= K - 1，
可见在这个范围下不会有多少种情况，因为K的最大值才1000。
算法流程
枚举两个数的余数，然后计算第三个数所需的余数，根据贪心算法并在对应余数组中取最大值。
1. 分类存储：
将所有数字按其对 K 取模的结果分成 K 个桶，即： arr[i] 存放所有 x 满足 x % K == i。
这样做的目的，是为了快速找出所有具有相同模值的数，为后续组合提供便利。
2. 排序每个桶：
为了后续能快速取出某个模值的最大值，对每个桶排序，这样能轻松获取每个模值中最大的元素。
3. 枚举前两个数模值 (i, j)：
你遍历所有 i, j ∈ [0, K)，对每一组 (i, j)：
- 从
arr[i]取最大值a - 从
arr[j]取最大值b
4. 根据前两个快速得出第三个模值k：
k = n * K - i - j(n >= 1, 0 <= k <= K - 1)
5. 特别处理下标冲突：
你保存了桶中最大的数后还要回填，因为之后还会用到这些桶。每次取出最大值后记得放回去。