场上确实想到贪心了（之前好像看过这个结论？？？）但是我就认为要每次用数字倒着乘，复杂度是n^2/m，然后就被200000 1的数据卡了
正确的方法是先排序，然后处理一个前缀和
ans[i] = a[i - m] + sum[i]
(正确性是显然的，因为对于ans[i - m]和ans[i]之间是刚好差了一个sum[i]所以可以在O(n)的复杂度处理）
#include <cstdio> #include <algorithm> using namespace std; const int N = 200010; long long sum[N], ans[N], a[N]; int main() { int n, m; scanf("%d %d", &n, &m); for (int i = 1; i <= n; i++) scanf("%lld", &a[i]); sort(a + 1, a + n + 1); for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i]; for (int i = 1; i <= n; i++) { if (i > m) ans[i] = ans[i - m] + sum[i]; else ans[i] = sum[i]; printf("%lld ", ans[i]); } return 0; }
Codeforces Round #600 (Div. 2) C. Sweets Eating
原文：https://www.cnblogs.com/cminus/p/11934882.html