题解 P5381 【[THUPC2019]不等式】

· · 题解

题意

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

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

\sum_{i=0}^k|a_i|*|x+\frac{b_i}{a_i}|

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

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

注意总个数可能爆int

Talk is cheap, show me the code.

码风很丑，大佬轻喷

#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;//完结撒花
}