选美

【题目描述】

一年一度的星哥选美又拉开了帷幕

N个人报名参加选拔，每个人都有着各自的相貌参数和身材参数（不大于 10000 的正整数）。你的任务是尽可能让更多人被星哥选中，而唯一要求就是，在这只队伍里面的每个人，都需满足以下不等式：

$A (H− h) +B(W− w) ≤ C$

其中H和W为这个人的相貌和身材， h和w为选中者中的最小相貌参数和最小身材参数，而A、 B、 C为三个不大于 10000 的正的整型常数。

现在请计算星哥最多可以选中多少人。

【输入格式】

第一行：一个整数： N(0<N<=2000)

第二行：三个分开的整数： A,B和C

第三行到第N+ 2行：每行有两个用空格分开的整数，分别表示一个人的相貌参数和身材参数

【输出格式】

第一行：最多被选的人数

【输入样例】

8
1 2 4
5 1
3 2
2 3
2 1
7 2
6 4
5 1
4 3

【输出样例】

5

题解

只有$n^2\log_2{n}$的算法

先按H排序

枚举每一个h

然后将他后面的部分再按w排序

由树状树状维护前缀和就可以求出来了

/*
 * @Author: WildRage 
 * @Date: 2017-08-06 17:57:21 
 * @Last Modified by: WildRage
 * @Last Modified time: 2017-08-07 19:11:10
 */
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
struct data
{
    int h, w;
} a[2005], b[2005];
int n, A, B, C, m;
int comp(const data &a, const data &b)
{
    return a.h < b.h;
}
int cmp(const data &a, const data &b)
{
    return a.w < b.w;
}
int c[2005];
int lowbit(int x)
{
    return x & (-x);
}
void add(int x, int w)
{
    for (int i = x; i <= m; i += lowbit(i))
        c[i] += w;
}
int sum(int x)
{
    int s = 0;
    for (int i = x; i; i -= lowbit(i))
        s += c[i];
    return s;
}
int ans = 0;
void solve(int from)
{
    int h_min = a[from].h, w_min;
    int all;
    memcpy(b, a, sizeof(b));
    memset(c, 0, sizeof(c));
    sort(b + from, b + n + 1, cmp);
    int Sum[2005], Hash[2005];
    for (int i = from; i <= n; i++)
        Hash[i] = Sum[i] = b[i].h * A + b[i].w * B;
    sort(Hash + from, Hash + n + 1);
    m = unique(Hash + from, Hash + n + 1) - Hash - 1;
    for (int i = from; i <= n; i++)
    {
        int x = upper_bound(Hash + from, Hash + m + 1, Sum[i]) - Hash - 1;
        add(x, 1);
    }
    for (int i = from; i <= n; i++)
    {
        w_min = b[i].w;
        all = C + A * h_min + B * w_min;
        int x = upper_bound(Hash + from, Hash + m + 1, all) - Hash - 1;
        ans = max(ans, sum(x));
        add(upper_bound(Hash + from, Hash + m + 1, Sum[i]) - Hash - 1, -1);
    }
}
int main()
{
    //freopen("beauty.in", "r", stdin);
    //freopen("beauty.out", "w", stdout);
    scanf("%d", &n);
    scanf("%d%d%d", &A, &B, &C);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d", &a[i].h, &a[i].w);
    }
    sort(a + 1, a + n + 1, comp);
    for (int i = 1; i <= n; i++)
        solve(i);
    printf("%d", ans);
}