本文主要是介绍Codeforces Round 910 (Div. 2) D. Absolute Beauty，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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;
}
这篇关于Codeforces Round 910 (Div. 2) D. Absolute Beauty的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
