设为首页 加入收藏

TOP

洛谷P4165 [SCOI2007]组队(排序 堆)
2018-12-03 16:09:36 】 浏览:18
Tags:洛谷 P4165 SCOI2007 组队 排序

题意

题目链接

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

编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇BZOJ4568: [Scoi2016]幸运数字(线.. 下一篇[bzoj1116][POI2008][CLO]

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(214) }