洛谷P4165 [SCOI2007]组队 题解

题目链接：P4165 [SCOI2007]组队

题意：

NBA每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为 \(\min V\)，身高最矮的球员高度为 \(\min H\)，那么这支球队的所有队员都应该满足: \[ A \times ( \mathtt{height} – \min H ) + B \times ( \mathtt{speed} – \min V ) \le C \] 其中 \(A,B,C\) 为给定的经验值。这个式子很容易理解，如果一个球队的球员速度和身高差距太大，会造成配合的不协调。

请问作为球队管理层的你，在 \(N\) 名选秀球员中，最多能有多少名符合条件的候选球员。

输入格式：

第一行四个数 \(N,A,B,C\) 下接 \(N\) 行每行两个数描述一个球员的 \(\mathtt{height}\) 和\(\mathtt{speed}\) 。

输出格式：

最多候选球员数目。

数据范围：

\(N \le 5\times 10^3\) ，\(A,B,C\) 均在长整型以内，\(\mathtt{height}\) 和 \(\mathtt{speed}\) 不大于 \(10^4\) 。

好像有人写了三维偏序，真流批

其实这题不需要三维偏序

考虑枚举 \(\min H\) ，然后我们会得到一个 \(\min V\) 的不等式 \[ V-\left(C - \frac{A\times (H-\min H)}{B}\right) \ge \min V \] 然后我们就可以算出每个球员在 \(\min H\) 确定的情况下

\(\min V\) 在哪个范围的时候，这个球员可以被选中，考虑差分。

最后枚举每个球员作为 \(\min V\) ，此时可以直接查询差分数组（要先做一遍前缀和哦）

注意特判 \(B=0\) 的情况，此时 \(\forall \min V \in [1,v_i]\) 可以选 \(v_i\) 。

时间复杂度 \(O(n \times \max\{n,v_i\})\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N ((int)(5e3+15))

int n,A,B,C,res=1,mx,h[N],t[N],v[N],cnt[N*2];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> A >> B >> C;
    for(int i=1; i<=n; i++)
        cin >> h[i] >> v[i],mx=max(mx,v[i]),t[i]=h[i];
    sort(t+1,t+1+n);
    int o = unique(t+1,t+1+n) - t - 1;
    for(int i=1; i<=o; i++)
    {
        memset(cnt,0,sizeof(cnt));
        for(int j=1; j<=n; j++)
        {
            if(h[j] >= t[i] && (A * (h[j] - t[i])) <= C)
            {
                int tl=1;
                if(B) tl=max(tl, v[j] -  (C - A*(h[j]-t[i])) / B );
                ++cnt[tl]; --cnt[v[j]+1];
                // minV in [tl, v[j]] is ok for j,
                // so minV in [tl, v[j]] can choose j.
            }
        }
        for(int j=2; j<=mx; j++) cnt[j] += cnt[j-1];
        for(int j=1; j<=n; j++) res = max(res, cnt[v[j]]);
    }
    cout << res << '\n';
    return 0;
}