题解 P5381 [THUPC2019]不等式

发表于 | 更新于 | 分类于 | 阅读次数：

题面

题意

给定$\{a_n\}$,$\{b_n\}$
求$\sum_{i=1}^k|a_ix+b_i|$ 的最小值$(\forall k\in[1,n])$

首先根据小学数学知识，我们把它转化为:

考虑实际意义，一条数轴上有$m$个点，要求数轴上一点，使该点到各点的距离和最小
显然， 当这个点为第$\frac{m+1}2$个点时为一个最优解(即中位数)

然后用平衡树维护中位数，并统计答案即可(当然你用两个堆也可以)

注意总个数可能爆$int$

Talk is cheap, show me the code.

码风很丑，大佬轻喷

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
#include <bits/stdc++.h>
using namespace std;
// 以下平衡树(无旋treap)
struct node {
    int rnd, cnt, ls, rs;
    long long size;
    double sum, key;
} t[500010];
inline int newnode(double key, int cnt) {
    static int Cnt = 0;
    t[++Cnt] = node{rand(), cnt, 0, 0, (long long)cnt, key * cnt, key};
    return Cnt;
}
inline void up(int x) {
    t[x].size = t[t[x].ls].size + t[t[x].rs].size + t[x].cnt;
    t[x].sum = t[t[x].ls].sum + t[t[x].rs].sum + t[x].key * t[x].cnt;
}
inline int merge(int a, int b) {
    if(a == 0 || b == 0) return a | b;
    if(t[a].rnd < t[b].rnd) return t[a].rs = merge(t[a].rs, b), up(a), a;
    return t[b].ls = merge(a, t[b].ls), up(b), b;
}
inline void split_key(int now, double k, int &x, int &y) {
    if(now == 0) x = y = 0;
    else if(t[now].key > k) y = now, split_key(t[now].ls, k, x, t[y].ls), up(y);
    else x = now, split_key(t[now].rs, k, t[x].rs, y), up(x);
}
inline void split_rank(int now, long long k, int &x, int &y) {
    if(now == 0) x = y = 0;
    else if(t[t[now].ls].size >= k) y = now, split_rank(t[now].ls, k, x, t[y].ls), up(y);
    else x = now, split_rank(t[now].rs, k - t[t[now].ls].size - t[now].cnt, t[x].rs, y), up(x);
}
inline double get_max(int now) {
    if(t[now].rs) return get_max(t[now].rs);
    return t[now].key;
}
//平衡树结束
int n, a[500010], b[500010], rt;
double lala;
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d", a + i);
    for(int i = 1; i <= n; i++) scanf("%d", b + i);
    for(int i = 1; i <= n; i++) {
        if(a[i] < 0) a[i] = -a[i], b[i] = -b[i]; //加绝对值
        int x, y;
        if(a[i] == 0) lala += abs(b[i]); //特判
        else {
            double add = -1.0 * b[i] / a[i];
            split_key(rt, add, x, y);
            rt = merge(merge(x, newnode(add, a[i])), y);
        }
        double mid;
        split_rank(rt, (t[rt].size + 1) / 2, x, y);
        mid = get_max(x);
        printf("%.10lf\n", lala + mid * t[x].size - t[x].sum + t[y].sum - mid * t[y].size);
        rt = merge(x, y);
    }
    return 0;//完结撒花
}