题意
?
思路
肯定出发点是去考虑伤害的贡献
注意到贡献是长为 k 的段的贡献加起来的,一段的贡献是 max(0, sum - s)
然后看,他让我们选一段子序列,注意到子序列内部无序,那其实就是子集,那就可以考虑排序贪心了
考虑从大到小排序就好了,其实就是从大到小选
我们要求每个 k 的答案,k 已经是 1e6了,剩下的要不就O(1)要不O(logn)
logn的话,考虑调和级数枚举(其实这个做法可以根据复杂度猜出来),那就是去枚举每段了
那就直接枚举每段算贡献即可
#include <bits/stdc++.h>
#define int long long
constexpr int N = 1e6 + 10;
constexpr int M = 1e4 + 10;
constexpr int mod = 1e9 + 7;
int n, s;
int a[N];
void solve() {
std::cin >> n >> s;
for (int i = 1; i <= n; i ++) {
std::cin >> a[i];
}
std::sort(a + 1, a + 1 + n, std::greater<int>());
for (int i = 1; i <= n; i ++) {
a[i] += a[i - 1];
}
for (int k = 1; k <= n; k ++) {
int ans = 0;
for (int i = 1; i <= n; i += k) {
int sum = a[std::min(n, i + k - 1)] - a[i - 1];
if (sum > s) {
ans += sum - s;
}else {
break;
}
}
std::cout << ans << "\n";
}
}
signed main(){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t = 1;
while(t --) {
solve();
}
return 0;
}
?