题解：P4165 [SCOI2007] 组队

· · 题解

~纪念模拟赛因狗屎搬题人开大数据未离散化导致的挂分~

~个人认为这题评紫是不是高了~

题意：

给出一些球员的身高和速度以及三个常数 A,B,C，请你选出一些球员。设这些球员中身高最矮为 minh，速度最小为 minv，求最多选出多少名球员使得对于任意球员满足 A \times (h - minh) + B \times (v - minv) \le C。

题解：

看见对于每个球员有两个信息，以及一条限制，想到一个类似于二维偏序的东西。

我们对于每个球员先以 h 为第一关键字排序。

首先我们枚举可能作为最小身高的球员 i。

那么对于所有 j \ge i，此时，可以保证选 j 能让最小身高合法。

那么对于球员 j，A \times (h_j - h_i) + B \times (v_j - minv) \le C。

我们把式子变换成关于未知数的，就有 minv \ge v_j - \frac{C - A \times (h_j - h_i)}{B}。

同时，对于每个球员 j 我们要保证 minv \le v_j。

所以，对于每个球员 j，当且仅当 minv 满足 v_j - \frac{C - A \times (h_j - h_i)}{B} \le minv \le v_j 时 minv 合法。

因此我们可以把满足 v_j - \frac{C - A \times (h_j - h_i)}{B} \le minv \le v_j 的 minv 的答案加一表示这个区间内的 minv 可选的球员个数加一，这里可以使用差分维护。

最后把差分数组还原并且对于所有身高合法的球员看一下他作为身高最小者对应的答案有几个取最大值即可。

代码

::::info[码风丑陋的代码]{open}

#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if(ch == '-'){
            f = -1;
        }
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
void write(int x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9){
        write(x / 10);
    }
    putchar(x % 10 + '0');
    return;
}
int N, m, A, B, C, ans, maxn, d[10005];
struct node{
    int h, v, cnt;
}t[10005], f[10005];
bool cmp(node x, node y){
    if(x.h == y.h){
        return x.v < y.v; 
    }
    return x.h < y.h;
}
signed main(){
    N = read(), A = read(), B = read(), C = read();
    for(int i = 1; i <= N; i++)
        t[i].h = read(), t[i].v = read(), t[i].cnt = 1;
    sort(t + 1, t + N + 1, cmp);
    for(int i = 1; i <= N; i++){//离散化 
        if(t[i].h == f[m].h && t[i].v == f[m].v)
            f[m].cnt++;
        else
            m++, f[m] = t[i];
    }
    for(int i = 1; i <= m; i++){//枚举身高最矮的球员 
        int minn = 1e18, maxn = 0;
        for(int j = i; j <= m; j++){//枚举所有身高合法的球员 
            if(A * (f[j].h - f[i].h) > C)//单论身高已经炸了的直接跳过 
                break;
            int minv = (B/*考虑到 B可能为 0 避免 RE，当 B为 0 时，minv 为任意非负数均合法*/ ? max(0ll, f[j].v - (C - A * (f[j].h - f[i].h)) / B) : 0);//表示最低合法最小速度
            d[minv] += f[j].cnt, d[f[j].v + 1] -= f[j].cnt;//表示速度在l-f[j].v之间的球员可以和j球员一队 
        }
        for(int j = 1; j <= 1e4; j++)
            d[j] += d[j - 1];//差分化为原数组 
        for(int j = i; j <= m; j++)
            ans = max(ans, d[f[j].v]);//统计答案 
        memset(d, 0, sizeof(d));//清空差分数组 
    }
    write(ans);
    return 0;
}

::::