hihoCoder--1469 优化延迟(二分+优先队列)

2/10/2017来源:ASP.NET技巧人气:808

题解

注意到SP(k)随着k增大而递减,因此可以在[1, N]区间内二分搜索k,对每一个k用优先队列计算SP(k). 时间复杂度:O(n∗logn∗logn)

#include <bits/stdc++.h> using namespace std; const int maxn = 100000 + 10; long long N, Q; int p[maxn]; long long SP(int k){ PRiority_queue<int> pq; long long sp = 0; int cnt = 1; for(int i = 1; i <= k; ++i) pq.push(p[i]); for(int i = k + 1; i <= N; ++i){ int val = pq.top(); pq.pop(); sp += val * cnt++; pq.push(p[i]); } while(!pq.empty()){ sp += pq.top() * cnt++; pq.pop(); } return sp; } int main(){ #ifndef ONLINE_JUDGE freopen("data.in", "r", stdin); #endif ios::sync_with_stdio(false); cin >> N >> Q; for(int i = 1; i <= N; ++i){ cin >> p[i]; } int l = 1, r = N, ans = -1; while(l <= r){ int k = (l + r) >> 1; if(SP(k) <= Q){ ans = k; r = k - 1; }else l = k + 1; } cout << ans << endl; return 0; }