AcWing 1262. 鱼塘钓鱼
原题链接
简单
作者:
homeffg
,
2021-02-07 23:14:25
,
所有人可见
,
阅读 996
只想到暴力枚举
时间复杂度 $O(TN\log{N})$
#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> PII;
const int N = 110;
int s[N], a[N], d[N];
int main() {
int n, T;
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> d[i];
//求间隔时间前缀和
for (int i = 2; i <= n; i++) {
cin >> s[i];
s[i] += s[i - 1];
}
cin >> T;
int ans = 0;
//枚举只在前i个池塘钓鱼
for (int i = 1; i <= n && s[i] <= T; i++) {
//由于只需要最大值,用堆存储
priority_queue<PII> q;
for (int j = 1; j <= i; j++) q.push({a[j], d[j]});
int t = T - s[i], res = 0;
//枚举除间隔外在钓鱼的每一分钟
for (int j = 1; j <= t; j++) {
auto p = q.top();
q.pop();
if (p.first <= 0) break;
res += p.first;
p.first -= p.second;//每分钟减少
q.push(p);//减少后入堆
}
ans = max(ans, res);
}
cout << ans << endl;
return 0;
}
这个复杂度不是n方T的么
用了堆优化每次求最大值是 $logN$
但是每次都要将前i个放入优先队列中,不是约等于n2
那里不包含T,是 $O(n^2)$,后面包含T的有一次出堆入堆,是 $O(nT\log{n})$
奥奥~明白了