牛客NOIP暑期七天营-普及组1-C丢失的题面
丢失的题面
https://ac.nowcoder.com/acm/contest/916/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; }