Blackops

初心易得，始终难守

0%

Wannafly挑战赛16 AB序列（三分求离散凹函数极值）

发表于 分类于 ， ，

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

给长度为$n$的序列$A$，长度为$m$的序列$B$。可以给A序列里每个元素加上$x$且$B$序列里每个元素减去$x$ ($x$可以是负数），问$\sum{|A_i|}+\sum{B_i}+|x|$的最小值

输入描述:

1
2
3
第一行两个整数分别表示n,m
接下来一行n个整数表示序列A
接下来一行m个整数表示序列B

输出描述:

1
输出一个整数表示答案

示例1

输入

1
2
3
4 5
-8 2 -4 10
5 -5 -4 -9 10

输出

1
57

备注:

$1\le n,m\le 10^5$
序列中的数为绝对值不超过$10^9$的整数

题目链接：Wannafly挑战赛16 AB序列

学习并记录一下整型三分的一种基本姿势，用$midl$表示$l…r$中的中间位置，用$midr$表示$midl…r$中的中间位置，然后看哪一端更符合要求，最后注意还要特判最后留下的$l$和$r$到底哪个最优即可。

Cf2wDS.png

代码：

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
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
#define INF 0x3f3f3f3f
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
#define pb(x) push_back(x)
#define sf(x) scanf("%d", &x)
#define all(a) (a).begin(),(a).end()
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define caseT int _T;scanf("%d",&_T);for (int q=1; q<=_T; ++q)
typedef pair<int, int> pii;
//typedef complex<double> cpx;
typedef long long ll;
const double PI = acos(-1.0);
const int N = 1e5 + 7;
ll a[N], b[N];
int n, m;

inline ll calc(ll x)
{
    ll w = 0;
    for (int i = 0; i < n; ++i)
        w += llabs(a[i] + x);
    for (int i = 0; i < m; ++i)
        w += llabs(b[i] - x);
    return w + llabs(x);
}
int main(void)
{
    int i;
    sf(n), sf(m);
    for (i = 0; i < n; ++i)
        scanf("%lld", a + i);
    for (i = 0; i < m; ++i)
        scanf("%lld", b + i);
    ll l = -1e9 - 10, r = 1e9 + 10, midl, midr;
    while (l + 1 < r)
    {
        midl = (l + r) >> 1, midr = (midl + r) >> 1;
        if (calc(midl) <= calc(midr))
            r = midr;
        else
            l = midl;
    }
    printf("%lld\n", min(calc(l), calc(r)));
    return 0;
}