【贪心】牛客练习赛90 C

发布时间:2023年12月20日

登录—专业IT笔试面试备考平台_牛客网

题意

?

思路

肯定出发点是去考虑伤害的贡献

注意到贡献是长为 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;
}

?

文章来源:https://blog.csdn.net/weixin_62528401/article/details/135097926
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。