洛谷P4165 [SCOI2007]组队(排序 堆)
程序员文章站
2022-05-30 21:57:18
题意 "题目链接" Sol 跟我一起大喊:n方过百万,暴力踩标算! 一个很显然的思路是枚举$H, S$的最小值算,复杂度$O(n^3)$ 我们可以把式子整理一下,变成 $$A H_i + B S_i \leqslant C + AminH + BminS$$ 首先按$H$排序 考虑去从大到小枚举$A ......
题意
sol
跟我一起大喊:n方过百万,暴力踩标算!
一个很显然的思路是枚举\(h, s\)的最小值算,复杂度\(o(n^3)\)
我们可以把式子整理一下,变成
\[a h_i + b s_i \leqslant c + aminh + bmins\]
首先按\(h\)排序
考虑去从大到小枚举\(aminh\),同时用个vector \(n^2\)维护\(s\)序列(直接\(lowerbound + insert\))
再从大到小枚举\(bmins\),同时用堆维护\(ah_i + b_i\),当堆顶不满足条件的时候直接弹掉即可,用堆内元素更新答案
没错在bzoj上被卡了
#include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/hash_policy.hpp> #include<ext/pb_ds/priority_queue.hpp> #define pair pair<int, int> #define mp make_pair #define fi first #define se second using namespace std; const int maxn = 5001, mod = 1e9 + 7; inline int read() { char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, a, b, c, th[maxn], ts[maxn]; struct node { int h, s, id; bool operator < (const node &rhs) const { return h < rhs.h; } }a[maxn]; signed main() { n = read(); a = read(); b = read(); c = read(); for(int i = 1; i <= n; i++) th[i] = a[i].h = read(), a[i].s = read(); sort(th + 1, th + n + 1); sort(a + 1, a + n + 1); int ans = 0; vector<pair> v; for(int i = n; i >= 1; i--) { pair now = mp(b * a[i].s, a * a[i].h + b * a[i].s); v.insert(lower_bound(v.begin(), v.end(), now), now); //__gnu_pbds::priority_queue<int> q; priority_queue<int> q; int r = v.size() - 1; for(int j = r; j >= 0; j--) { q.push(v[j].se); while(!q.empty() && q.top() > c + a * th[i] + v[j].fi) q.pop(); ans = max(ans, (int)q.size()); } } cout << ans; return 0; } /* */