D. Absolute Beauty
有兩個長度為 n n n 的整數數組 a 1 , a 2 , … , a n a_1,a_2,\ldots,a_n a1?,a2?,…,an? 和 b 1 , b 2 , … , b n b_1,b_2,\ldots,b_n b1?,b2?,…,bn? 。他將數組 b b b 的美麗值定義為
∑ i = 1 n ∣ a i ? b i ∣ . \sum_{i=1}^{n} |a_i - b_i|. i=1∑n?∣ai??bi?∣.
這里， ∣ x ∣ |x| ∣x∣ 表示 x x x 的絕對值。
最多可以進行一次以下操作：
- 選擇兩個索引 i i i 和 j j j （ 1 ≤ i < j ≤ n 1 \leq i < j \leq n 1≤i<j≤n ），并交換 b i b_i bi? 和 b j b_j bj? 的值。
幫助他找出數組 b b b 在進行一次交換后的最大美麗值。
思路：
我們將 a i a_i ai?和 b i b_i bi?看作一組線段的左右端點，容易發現，只有當兩段線段不相交時，我們可以將其對答案的貢獻變大，其貢獻為間隔距離的兩倍。所以我們維護最小右端點和最大左端點即可。
#include <bits/stdc++.h>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;
}
)
)
