洛谷P4165 [SCOI2007]组队(排序堆)

缺乏、安全感 2022-03-27 14:12 202阅读 0赞

## 题意 ##

[题目链接][Link 1]

## 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;
    }
    /*
    */

[Link 1]: https://www.luogu.org/problemnew/show/P4165