LG-P4264 [USACO18FEB]Teleportation S Solution

更好的阅读体验戳此进入

题面

数轴上存在 $n$$n$ 对 $a_i,b_i$$a_i, b_i$ 表示有一坨牛粪需要从 $a_i$$a_i$ 送到 $b_i$$b_i$ 并贡献 $d_i=|a_i-b_i|$$d_i = \vert a_i - b_i \vert$，数轴上存在一个起点为 $0$$0$，终点为 $y$$y$ 的便便传送门，可以在 $0$$0$ 的贡献下将牛粪从 $0$$0$ 传送到 $y$$y$，同样贡献为不用传送门走的距离，最小化贡献和，求最小值。

$1\le n\le {10}^5,-{10}^8\le a_i,b_i\le {10}^8$$1 \le n \le 10^5, -10^8 \le a_i, b_i \le 10^8$。

Solution

这道题告诉我们，题做不出来的时候要多去去厕所，去溜达一圈之后或许就突然想明白了。。

我感觉还算是一道挺有意思的题，比较奇妙，难度适中，蓝色评的也很合理。

显然当 $y$$y$ 确定后对于每一对 $a_i,b_i$$a_i, b_i$ 的贡献即为 $f(y{)}_i=min(|a_i-b_i|,|a_i|+|y-b_i|)$$f(y)_i = \min(\vert a_i - b_i \vert, \vert a_i \vert + \vert y - b_i \vert)$，我们的答案即为 $\sum _{i=1}^{n}f(y{)}_i$$\sum_{i = 1}^n f(y)_i$。

此时显然如果有 $|a_i-b_i|<|a_i|$$\vert a_i - b_i \vert \lt \vert a_i \vert$，解一下就是 $a_i\ge b_i>0\vee 0\le a_i<b_i<2a_i\vee 0>a_i>b_i>2a_i\vee a_i<b_i<0$$a_i \ge b_i \gt 0 \vee 0 \le a_i \lt b_i \lt 2a_i \vee 0 \gt a_i \gt b_i \gt 2a_i \vee a_i \lt b_i \lt 0$，那么一定不走传送门，也就是选前者，这样的话对于这个 $f(y{)}_i$$f(y)_i$ 就是一条直线，不过这一大坨不等式看着就很阴间，画个图吧：

观察发现剩下的可能性就只有 $0\le 2a_i<b_i\vee b_i<2a_i\le 0\vee a_i<0<b_i\vee b_i<0<a_i$$0 \le 2a_i \lt b_i \vee b_i \lt2a_i \le 0 \vee a_i \lt 0 \lt b_i \vee b_i \lt 0 \lt a_i$ 了，而这一段区间则与 $y$$y$ 相关，需要额外讨论一下。

此时的原式为 $f(y{)}_i=min(|a_i-b_i|,|a_i|+|y-b_i|)$$f(y)_i = \min(\vert a_i - b_i \vert, \vert a_i \vert + \vert y - b_i \vert)$，考虑分类讨论，如在 $0\le 2a_i<b_i$$0 \le 2a_i \lt b_i$ 的条件下，原式转化为 $min(b_i-a_i,a_i+|y-b_i|)$$\min(b_i - a_i, a_i + \vert y - b_i \vert)$，然后把 $y$$y$ 和 $b_i$$b_i$ 之间的关系讨论一下（这里就很简单了，不多赘述，注意一下 $b_i<2b_i-2a_i$$b_i \lt 2b_i - 2a_i$ 在条件下恒成立即可），最终可以写成一下柿子：

$0\le 2a_i<b_i$$0 \le 2a_i \lt b_i$：

然后在 $b_i<2a_i\le 0$$b_i \lt2a_i \le 0$ 同理可以推出：

$b_i<2a_i\le 0$$b_i \lt2a_i \le 0$：

剩下的两个区间也同理推导一下即可：

$a_i<0<b_i$$a_i \lt 0 \lt b_i$：

$b_i<0<a_i$$b_i \lt 0 \lt a_i$：

现在我们也就能确定下来每一条 $f(y{)}_i$$f(y)_i$ 的形状了，都是类似下图的形状，只是 “转折点” 不同，和 $y$$y$ 无关的认为其没有转折点即可。

此时我们就需要考虑一下求 $\sum _{i=1}^{n}f(y{)}_i$$\sum_{i = 1}^nf(y)_i$ 了。

不难想到 $O(n)$$O(n)$ 记录一下每一条线的 “转折点” 的位置，建立一个差分数组，然后每条线段斜率变为 $-1$$-1$ 之后对应位置加上 $-1$$-1$，斜率变为 $1$$1$ 之后加上 $2$$2$，变回与 $y$$y$ 相关之后再加上 $-1$$-1$，然后我们把差分数组做个前缀和，这样当前的前缀和数组的值就是 $i$$i$ 相对 $i-1$$i - 1$ 的总答案变化量，对于 $0$$0$ 处我们认为其为 $\sum _{i=1}^n|a_i-b_i|$$\sum_{i = 1}^n \vert a_i - b_i \vert$，然后在前缀和上再做一个前缀和，令其为 $su{m}_i$$sum_i$，则不难想到答案即为 $min\{su{m}_i\}$$\min\{sum_i\}$，然后这里因为坐标值域范围很大，所以考虑离散化，为了写着方便，直接开一个 map 存即可，排序也省了。

至此，我们就做完了这道奇怪的大分类讨论，复杂度 $O(n\log n)$$O(n \log n)$，卡在排序上。

Code

78
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template< typename T = int >
24
inline T read(void);
25

26
int N;
27
ll origin(0);
28
ll mn(LONG_LONG_MAX);
29
map < ll, ll > mp;
30
ll sum[310000]; int cnt(0);
31

32
void Insert(int p, int v){
33
    if(mp.find(p) == mp.end())mp.insert({p, v});
34
    else mp[p] += v;
35
}
36
void InsertAll(int sp1, int sp2, int sp3){
37
    Insert(sp1, -1);
38
    Insert(sp2, 2);
39
    Insert(sp3, -1);
40
}
41

42
int main(){
43
    N = read();
44
    for(int i = 1; i <= N; ++i){
45
        int a = read(), b = read();
46
        origin += abs(a - b);
47
        if(0 <= 2 * a && 2 * a < b)InsertAll(2 * a, b, 2 * b - 2 * a);
48
        else if(b < 2 * a && 2 * a <= 0)InsertAll(2 * b - 2 * a, b, 2 * a);
49
        else if(a < 0 && 0 < b)InsertAll(0, b, 2 * b);
50
        else if(b < 0 && 0 < a)InsertAll(2 * b, b, 0);
51
    }
52
    ll cur(0), sum(origin); int lft(INT_MIN);
53
    mn = origin;
54
    for(auto v : mp){
55
        sum += (ll)cur * (v.first - lft);
56
        cur += v.second, lft = v.first;
57
        mn = min(mn, sum);
58
    }
59
    printf("%lld\n", mn);
60
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
61
    return 0;
62
}
63

64
template < typename T >
65
inline T read(void){
66
    T ret(0);
67
    short flag(1);
68
    char c = getchar();
69
    while(c != '-' && !isdigit(c))c = getchar();
70
    if(c == '-')flag = -1, c = getchar();
71
    while(isdigit(c)){
72
        ret *= 10;
73
        ret += int(c - '0');
74
        c = getchar();
75
    }
76
    ret *= flag;
77
    return ret;
78
}

UPD

update-2022_11_07 初稿