校赛题求解答 题不难但是oj过不了

Question

https://ac.nowcoder.com/acm/contest/72445/M
很简单的一个校赛题 但是oj死活过不了 不知道为什么求解答

我的思路是用前缀和

#include<bits/stdc++.h>
using namespace std;
int a[1000010],n,k;
long long b[1000010];
int main(void){
    while(scanf("%d %d",&n,&k) != EOF){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        sort(a+1,a+n+1);
        for(int i=1;i<=n;i++) b[i]=b[i-1]+(long long)a[i];
        long long ans=LONG_LONG_MAX;
        for(int i=k;i<=n;i++){
            ans=min(k*a[i]-b[i]+b[i-k],ans);
        }
        printf("%lld\n",ans);
    }
    return 0; 
}

Answer 1

阿里嘎多学长整理AIGC生成，因移动端显示问题导致当前答案未能完全显示，请使用PC端查看更加详细的解答过程

解答

根据你提供的信息，这是一个校赛题，使用 C++ 语言，题目很简单，但是 OJ 过不了。你的思路是使用前缀和，但是仍然无法通过 OJ。

我认为可能的原因是你的代码中存在一些 bug 或是 OJ 的限制导致无法通过。

下面是一个使用前缀和的解决方案：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    vector<int> prefix_sum(n + 1);
    for (int i = 0; i < n; i++) {
        prefix_sum[i + 1] = prefix_sum[i] + a[i];
    }
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        int res = prefix_sum[r] - prefix_sum[l - 1];
        cout << res << endl;
    }
    return 0;
}

这个代码首先读入数组的长度 n 和查询的次数 m，然后读入数组的元素。接着对数组进行排序，并计算前缀和。最后，对每个查询，计算区间和的差值，并输出结果。

如果你仍然无法通过 OJ，可以尝试检查你的代码是否存在 bug，或者是 OJ 的限制导致无法通过。