Codeforces Round 910 (Div. 2) D. Absolute Beauty

D. Absolute Beauty

有两个长度为 $n$ 的整数数组 $a_1,a_2,\dots ,a_n$ 和 $b_1,b_2,\dots ,b_n$ 。他将数组 $b$ 的美丽值定义为

$$\sum _{i=1}^n|a_i-b_i|.$$
这里， $|x|$ 表示 $x$ 的绝对值。

最多可以进行一次以下操作：

• 选择两个索引 $i$ 和 $j$ （ $1\le i<j\le n$ ），并交换 $b_i$ 和 $b_j$ 的值。

帮助他找出数组 $b$ 在进行一次交换后的最大美丽值。

思路：
我们将$a_i$和$b_i$看作一组线段的左右端点，容易发现，只有当两段线段不相交时，我们可以将其对答案的贡献变大，其贡献为间隔距离的两倍。所以我们维护最小右端点和最大左端点即可。

#include 

using namespace std;
const int N = 1e6 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9 + 7;
const int maxv = 4e6 + 5;
// #define endl "\n"

void solve()
{
    int n;
    cin>>n;
    vector<ll> a(n+5),b(n+5);
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) cin>>b[i];
    ll ans=0;
    ll minv=1e9,maxv=0;
    for(int i=1;i<=n;i++){
        ans+=abs(a[i]-b[i]);
        if(a[i]>b[i]) swap(a[i],b[i]);
        minv=min(minv,b[i]),maxv=max(maxv,a[i]);
    }
    if(minv<maxv) ans+=(maxv-minv)*2;
    cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    t = 1;
    cin>>t;
    while (t--)
    {
        solve();
    }
    system("pause");
    return 0;
}
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