BZOJ1071 [SCOI2007]组队
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; }