洛谷 P4264 题解

admin 2021-06-20 PM 108℃ 0条

题目链接

分析

对于确定的 $y$,有 $dis=\sum_{i=1}^n\min(|a_i-b_i|,|a_i|+|b_i-y|)$。

设 $g_i(y)=\min(|a_i-b_i|,|a_i|+|b_i-y|)$。

设 $f(y)=\sum_{i=1}^ng_i(y)$,则 $ans=\min \{f(y)\}$。

显然 $f(y)$ 在 $y=b_i$ 时取最小值。

对于 $1\le i\le n$:

若 $|a_i-b_i|\le |a_i|$,则 $g_i(y)$ 的图像为一条直线 $y=|a_i-b_i|$。

若 $|a_i-b_i|>|a_i|$,则 $g_i(y)$ 为一个单谷函数,如下图:

P4264-1.png

容易知道 $|a_i-b_i|=|a_i|+|x_A-b_i|=|a_i|+|x_C-b_i|$,且 $k_{AB}=-1,k_{BC}=1$,$x_B=b_i$。

解得 $x_A=b_i-|a_i-b_i|+|a_i|$,$x_C=b_i+|a_i-b_i|-|a_i|$。

将 $x_A,x_B,x_C$ 称为“关键点”。对斜率做差分,在 $x_A,x_C$ 处标 -1,在 $x_B$ 标 2,只需要先求出 $\sum_{i=1}^n|a_i-b_i|$,然后在每一个关键点进行修改即可。

解决

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>

using namespace std;

const int N = 100005;
int n, a, b, tot, sum;
long long res, ans;

struct diff
{
    int val, pos;
    bool operator<(const diff &other) const
    {
        return pos < other.pos;
    }
    diff(int val, int pos): val(val), pos(pos)
    {
    }
    diff(): val(0), pos(0)
    {
    }
} d[N * 3];

template<typename T>
void read(T &ret)
{
    ret = 0;
    char ch = getchar(), flag = 0;
    while ((ch < '0' || ch > '9') && ch != '-')
        ch = getchar();
    if (ch == '-')
        ch = getchar(), flag = 1;
    while (ch >= '0' && ch <= '9')
        ret = ret * 10 + ch - '0', ch = getchar();
    if (flag)
        ret = -ret;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        read(a), read(b);
        int x = abs(a - b), y = abs(a);
        if (x > y)
            d[++tot] = diff(-1, b - x + y), d[++tot] = diff(2, b), d[++tot] = diff(-1, b + x - y);
        res = res + x;
    }
    ans = res;
    // cout << "res = " << res << endl;
    sort(d + 1, d + tot + 1);
    for (int i = 1, j = 1; i <= tot;)
    {
        while (d[j].pos == d[i].pos && j <= tot)
            sum += d[j].val, res = res + (d[j + 1].pos - d[j].pos) * sum, j++;
        i = j, ans = min(ans, res);
    }
    cout << ans << endl;
    return 0;
}

非特殊说明,本博所有文章均为博主原创。

评论啦~