牛客NOIP暑期七天营-普及组1-C丢失的题面

题目大意：阅读程序，优化时间复杂度，过掉所有数据。

# 原代码
int mod = 1e9 + 7;
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> a[i];
for(int j = 1; j <= n; ++j) {
    for(int i = 1; i <= n; ++i) {
        if(i < j) continue;
        for(int k = 0; k < i; ++k) {
            f[i][j] = max(f[i][j], f[k][j - 1] + a[i]);
            f[i][j] = max(f[i][j], f[k][j]);
        }
    }
}
int ans = 0;
for(int i = 1; i <= n; ++i) {
    ans = (ans + f[i][m]) % mod;
}
cout << ans << "\n";

程序功能：f[i][j]表示前i个数中最大的j个数的和（j >= i）。

用优先队列记录最大的m个数，每进来一个数，弹出最小的，保留最大的m个。
在压入和弹出过程中，记录优先队列中的元素之和，累加起来就是答案。

#include <bits/stdc++.h>
using namespace std;
int n, m, i, j, k, mo=1e9+7;
long long s, ans;
priority_queue <int> q;
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        scanf("%d", &k);
        s = s + k;
        q.push(-k);
        if(i > m){
            s = s + q.top();
            q.pop();
        }
        if(i >= m) ans = (ans+s) % mo;
    }
    printf("%lld\n", ans%mo);
    return 0;
}