壊すとword│E-olv

menu icon

BZOJ1071 [SCOI2007]组队

2015.02.03 08:46 Tue| 3 visits oi_2015| 2015_刷题日常| Text

Solution

其实，原题目的名称是“组队难题”。为什么难题两个字不见了？

（我这 sx 因为读入反了卡了一晚上 T^T

来看官方题解：

很容易得到一个 $\mathcal O(N^3)$ 的算法：枚举身高最矮和速度最慢的两个球员，然后再把其他队员都扫描一次，能加入就加入。

这样的算法有着很多的冗余。假如我们设一个球员用 $(h,v)$ 来描述（分别表示高度和速度）。把它看做平面坐标系上的坐标。那么枚举最小高度 $minH$ 和最小速度 $minV$ 以后，我们的目的就是在 $(minH,minV)$ 的右上方查找有多少个点满足 $(A*h+B*v)-(A*minH+B*minV)<=C$。

那么还是利用 $\mathcal O(N^3)$ 算法的思想，我们来做些优化：

如果当前我们已经求出 $(minH,minV)$ 对应的点集为 $S$ ，那么如果我们保持 $minH$ 不动，$minV+1$，那么 $S$ 会发生什么变化呢？

因为S中的所有元素都满足 $(A*h+B*v)-(A*minH+B*minV)<=C$，那么当 $minV$ 增大时，原集合元素同样满足 $(A*h+B*v)-(A*minH+B*(minV+1))<=C$。

  • $S$ 中 $V=minV$ 的点要从集合中删除。
  • $S$ 中要添加一些点进来。

那么可以设计一个新的扫描算法：

1． 先把所有点按 $A*h+B*v$ 从小到大排序

2． 枚举最小高度 $minH$

3． 从左到右枚举 $minV$ ，每次 $minV+1$ 转移时，将原答案集合中的在左边界上的点删除，然后把点向后扫描，把能加入的点加入集合。

因为每个点只会进入集合一次，删除一次，所以处理总时间为 $\mathcal O(N^2)$。

如果利用 STL 中的优先队列维护，时间复杂度 $\mathcal O(N^2\log N)$，可是仍然很快 >o<

Code

#include <bits/stdc++.h>
using namespace std;

#define N 5005

long long n, a, b, c;

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

struct data
{
    int h, v; long long w;
    data() {}
    data(long long _h, long long _v)
    : h(_h), v(_v) { w = h * a + v * b; }
    inline bool operator <(const data &d) const { return w < d.w; }
} d[N];

priority_queue<data> q;

inline bool cmp(const data &x, const data &y) { return x.h > y.h; }

int main()
{
    cin >> n >> a >> b >> c;
    for (int x, y, i = 1; i <= n; ++i)
        x = read(), y = read(), d[i] = data(x, y);
    sort(d + 1, d + n + 1, cmp);
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        while (!q.empty()) q.pop();
        int minh = d[i].h, minv = d[i].v;
        for (int j = 1; j <= n; ++j)
        {
            if (d[i].w - minh * a - minv * b > c) break;
            if (d[j].w - minh * a - minv * b > c) continue;
            minh = min(minh, d[j].h);
            if (d[j].v >= minv) q.push(d[j]);
            while (!q.empty() && q.top().w - minh * a - minv * b > c)
                q.pop();
            ans = max(ans, int(q.size()));
        }
    }
    cout << ans << endl;
}
Newer