给定一个正整数数组a，可以对数组元素进行两种操作，使得数组a的每一个元素都可以被k整除，最少的操作数是多少。 初始x = 0 1、选择一个a[i]，使a[i] = a[i] + x，然后x = x + 1; 2、仅仅使x = x + 1;
一个数x，如果想被k整除，需要加上k - x%k + nk，n>=0 对于需要加上相同数的数组元素，例如a[m]，a[n]，a[p]，都需要加上x才能被k整除，那么当第一个a[m]加上x后，x = x + 1 a[n]需要等待x = x + k后才能加上自己，加上之后x = x + k + 1 a[p]需要等待x = x + 2k后才能加上自己，加上后x = x + 2 * k + 1 那么x 最大是多少呢？由上面的例子可以看出，x随着同余数组元素的个数而增加，当有n个元素都需要加上x时，x = x + (n - 1)*k，所以我们需要找到都需要加上k - a % k元素数量的最大值，假设这个数量是cnt，需要加上的初始值为maxn = k - a % k，所以ans = maxn +(cnt -1) * k + 1; +1是因为x需要由0变到1，需要一步操作 同时我们可以看到x还与初始的x有关，所以当数量cnt相同时，应选择k - a%k较大的那个数 用map记录需要加上同一个数的元素数量 当cnt = 0时说明，map里没有元素，都被k整除，输出0 需要开long long
#include <iostream> #include <map> using namespace std; typedef long long ll; int main() { int T; cin >> T; while (T--) { map<ll, ll> mp; ll n, k, x; cin >> n >> k; for (int i = 0; i < n; ++i) { cin >> x; if (x % k) mp[k - x % k]++; } ll maxn = 0, cnt = 0; for (auto i : mp) { if (i.second >= cnt) { maxn = i.first; cnt = i.second; } } if (cnt == 0) cout << 0 << endl; else cout << maxn + (cnt - 1) * k + 1 << endl; } system("pause"); return 0; }Alice 和 Bob 一起读书，每人需要从他们喜欢的书里选k本书阅读，每本书都有自己的阅读时间，怎样使总的阅读时间最少。Alice和Bob读同一本书只算一次阅读时间。
贪心（排序）和枚举，前缀和也用到了 对书进行分类 a[i]为只有Alice喜欢读的书 b[i]为只有Bob喜欢读的书 c[i]为他们都喜欢读的书 从a[i]中选x本，b[i]选y本，c[i]选z本。x + z = k，y + z = k，那么x = y。对x进行枚举。 如果x + z < k 或者y + z < k说明无解 注意数组越界的问题，即枚举的边界。
#include <iostream> #include <algorithm> using namespace std; const int N = 2e5 + 5; int a[N], b[N], c[N]; int main() { int n, k; cin >> n >> k; int x, y, z, cnta = 0, cntb = 0, cntc = 0; for (int i = 0; i < n; ++i) { cin >> x >> y >> z; if (y) if (z) c[++cntc] = x; else a[++cnta] = x; else if(z) b[++cntb] = x; } sort(a + 1, a + cnta + 1); sort(b + 1, b + cntb + 1); sort(c + 1, c + cntc + 1); for (int i = 1; i <= cnta; ++i) a[i] = a[i - 1] + a[i]; for (int i = 1; i <= cntb; ++i) b[i] = b[i - 1] + b[i]; for (int i = 1; i <= cntc; ++i) c[i] = c[i - 1] + c[i]; int cnt = min(k, min(cnta, cntb)); int ans = 0x7fffffff; if ((cnta + cntc < k) || (cntb + cntc < k)) cout << "-1"; else { for (int i = max(0, k - cntc); i <= cnt; ++i) { if ((c[k - i] || i == k) && a[i] + b[i] + c[k - i] < ans) ans = a[i] + b[i] + c[k - i]; } cout << ans; } system("pause"); return 0; }