0%

USACO 2007 January Gold T3 Cow School Solution

题目大意

有 $n$ 次考试,第 $i$ 次的满分为 $b_i$,你的得分为 $a_i$,你可以删去 $d$ 次考试,从而你最后的分数为剩下的得分与剩下的总分之比,现存在一种方案,即删去 $\dfrac{a_i}{b_i}$ 最小的 $d$ 次考试,你可以任意删去 $d$ 个考试,求所有的 $d$,使得存在一个最后分数更高的方案。

$n\le 5\times 10^4$。

思路

显然可以对所有考试排序预处理出每个 $d$ 的原始方案所得分数 $\dfrac{S_d}{T_d}$。

考虑暴力,如果一个 $d$ 合法,则可以找到 $n-d$ 次考试,使得 $\dfrac{\sum a_{p_i}}{\sum b_{p_i}}>\dfrac{S_d}{T_d}$,其中 $p$ 表示一个方案的的下标集合。

问题转化为求 $\max\left\{\dfrac{\sum a_{p_i}}{\sum b_{p_i}}\right\}$,可以用 0/1 分数规划 + 0/1 背包在 $O(n^2\log n)$ 的时间复杂度下解决。

更进一步,如果一个 $d$ 合法,则可以在原始方案中替换一个 $i$ 变为 $j$,其中 $i\le d < j\le n$,使得方案更优,即 $\dfrac{S_d-a_i+a_j}{T_d-a_i+a_j}>\dfrac{S_d}{T_d}$,化简得 $b_iS_d-a_iT_d< b_jS_d-a_jT_d$,设
$$
f(d)=\min\{b_iS_d-a_iT_d\}(1\le i\le d)
$$
$$
g(d)=\max\{b_iS_d-a_iT_d\}(d< i\le n)
$$
则 $d$ 可以作为一个合法方案,当且仅当 $f(d)< g(d)$,可以 $O(n^2)$ 枚举解决。

考虑优化,发现这个式子很像斜率优化。

以 $f(d)$ 为例,原式可化为 $\dfrac{f(d)}{S_d}=\min\left\{b_i-\dfrac{T_d}{S_d}a_i\right\}$。

这里 $b=\dfrac{f(d)}{S_d}, y=b_i, k=\dfrac{T_d}{S_d}, x=a_i$。即 $b=\min\{y-kx\}$,可以维护一个下凸包,以保证决策最优。

与一般的斜率优化不同的是,这题的横坐标 $x$ 并不是递增的,即无法直接通过一般的数据结构(单调队列,单调栈)维护,这里通过 CDQ 分治维护。

在分治时维护凸包,先保证左半部分的横坐标 $x$ 递增(用归并排序保证时间复杂度),计算左半部分的凸包对右半部分的 $f(d)$ 的影响,不断向下递归即可解决问题。

最后,考虑 $k=\dfrac{T_d}{S_d}$ 的单调性。可以先证明 $\dfrac{b_1}{a_1}>\dfrac{b_1+b_2}{a_1+a_2}$(因为我们对考试进行了排序,即保证了 $\dfrac{a_i}{b_i}< \dfrac{a_j}{b_j}(i< j)$),然后用数学归纳法可以得出 $\dfrac{T_d}{S_d}$ 单调递减。根据斜率优化的基本操作,计算 $f$ 时用单调栈维护凸包,计算 $g$ 时用单调栈维护,即可在 $O(n\log n)$ 的时间复杂度下解决问题。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
const int MAXN = 100000 + 5;

int n, S[MAXN], T[MAXN], q[MAXN];
long long f[MAXN], g[MAXN];

struct node {
int a, b;
bool operator < (const node A) {return 1.0 * a / b < 1.0 * A.a / A.b;}
} p[MAXN];

struct Query {int x, y;} Q[MAXN], tmp[MAXN];

long double slope(int i, int j) {
if (Q[i].x == Q[j].x) return Q[i].y < Q[j].y ? 1e18 : -1e18;
return 1.0 * (Q[i].y - Q[j].y) / (Q[i].x - Q[j].x);
}

void solve_f(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1, R = 0;
solve_f(l, mid);
for (int i = l; i <= mid; i++) {
while (R > 1 && slope(q[R - 1], q[R]) > slope(q[R], i)) R--;
q[++R] = i;
}
for (int i = mid + 1; i <= r; i++) {
while (R > 1 && slope(q[R - 1], q[R]) > 1.0 * T[i] / S[i]) R--;
f[i] = std::min(f[i], 1ll * Q[q[R]].y * S[i] - 1ll * Q[q[R]].x * T[i]);
}
solve_f(mid + 1, r);
for (int i = l, p1 = l, p2 = mid + 1; i <= r; i++)
if (p2 > r || (p1 <= mid && Q[p1].x < Q[p2].x)) tmp[i] = Q[p1++];
else tmp[i] = Q[p2++];
for (int i = l; i <= r; i++) Q[i] = tmp[i];
}

void solve_g(int l, int r) {
if (l == r) return;
int mid = (l + r) >> 1, R = 0, L = 1;
solve_g(mid + 1, r);
for (int i = mid + 1; i <= r; i++) {
while (L < R && slope(q[R - 1], q[R]) < slope(q[R], i)) R--;
q[++R] = i;
}
for (int i = l; i <= mid; i++) {
while (L < R && slope(q[L], q[L + 1]) > 1.0 * T[i] / S[i]) L++;
g[i] = std::max(g[i], 1ll * Q[q[L]].y * S[i] - 1ll * Q[q[L]].x * T[i]);
}
solve_g(l, mid);
for (int i = l, p1 = l, p2 = mid + 1; i <= r; i++)
if (p2 > r || (p1 <= mid && Q[p1].x < Q[p2].x)) tmp[i] = Q[p1++];
else tmp[i] = Q[p2++];
for (int i = l; i <= r; i++) Q[i] = tmp[i];
}

std::vector<int> ans;

int main() {
read(n);
for (int i = 1; i <= n; i++) read(p[i].a, p[i].b);
std::sort(p + 1, p + n + 1);
for (int i = n - 1; i; i--) S[i] = S[i + 1] + p[i + 1].a, T[i] = T[i + 1] + p[i + 1].b;
for (int i = 1; i <= n; i++) Q[i] = Query{p[i].a, p[i].b}, f[i] = 1ll * p[i].b * S[i] - 1ll * p[i].a * T[i];
solve_f(1, n);
memset(g, 0xcf, sizeof(g));
for (int i = 1; i <= n; i++) Q[i] = Query{p[i].a, p[i].b};
solve_g(1, n);
for (int i = 1; i <= n; i++)
if (f[i] < g[i]) ans.push_back(i);
write(ans.size(), '\n');
for (auto res : ans) write(res, '\n');
return 0;
}