AcWing 1234 倍数问题
众所周知,小葱同学擅长计算,尤其擅长计算一个数是否是另外一个数的倍数。
但小葱只擅长两个数的情况,当有很多个数之后就会比较苦恼。
现在小葱给了你 n 个数,希望你从这 n 个数中找到三个数,使得这三个数的和是 K 的倍数,且这个和最大。
数据保证一定有解。
输入格式
第一行包括 2 个正整数 n, K 。
第二行 n 个正整数,代表给定的 n 个数。
输出格式
输出一行一个整数代表所求的和。
数据范围
1 ≤ n ≤ 10^5 ,
1 ≤ K ≤ 10^3 ,
给定的 n 个数均不超过 10^8
输入样例:
4 3
1 2 3 4
输出样例:
9
算法1(288 ms):
时间复杂度:O(n + m^2)。n, m 分别为给定的数据的个数,模数。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int M = 1000;
int n, m;
vector<int> buckets[M]; // buckets[i] 维护所有 == i mod m 的数
int cnt[M]; // 维护每个桶里的数据个数
int get_sum(int i, int j, int k) {
if (k < j || k >= m) { // check if 0 <= i <= j <= k < m
return 0;
}
int res = 0;
if (!cnt[i]) {
return 0; // 如果 i 不合法, 直接返回 0
}
res += buckets[i][--cnt[i]]; // *尝试选择 i
if (!cnt[j]) {
cnt[i]++; // 如果 j 不合法, 复原 i
return 0;
}
res += buckets[j][--cnt[j]]; // **尝试选择 j
if (!cnt[k]) {
cnt[i]++; cnt[j]++; // 如果 k 不合法, 复原 i 和 j
return 0;
}
res += buckets[k][--cnt[k]]; // ***尝试选择 k
cnt[i]++; cnt[j]++; cnt[k]++; // i, j, k 均合法, 计算完后复原 i, j, k
return res;
}
int get_ans() {
for (int i = 0; i < m; i++) {
sort(buckets[i].begin(), buckets[i].end());
cnt[i] = buckets[i].size();
}
int res = 0;
for (int i = 0; i < m; i++) {
for (int j = i; j < m; j++) {
res = max(res, get_sum(i, j, 0 - i - j)); // i + j + k == m * 0
res = max(res, get_sum(i, j, m - i - j)); // i + j + k == m * 1
res = max(res, get_sum(i, j, m * 2 - i - j)); // i + j + k == m * 2
}
}
return res;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
cin >> n >> m;
while (n--) {
int x;
cin >> x;
buckets[x % m].push_back(x);
}
cout << get_ans();
return 0;
}