将式子$\sum_{i=1}^n |a_i - b_i|$抽象成线段, 手玩一下发现更优情况只出现在相离线段
#include<bits/stdc++.h> using namespace std; #define endl "\n" #define int long long typedef long long ll; /* https://www.luogu.com.cn/problem/CF1898D 将式子抽象成线段 $\sum_{i=1}^n |a_i - b_i|$ */ const int N = 2e5 + 10; struct node { int l, r; } Seg[N]; int len[N]; signed main() { ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); int T = 1; cin >> T; while(T--) { int n; cin >> n; int sum = 0; for(int i = 1; i <= n; i++) cin >> Seg[i].l; for(int i = 1; i <= n; i++) { cin >> Seg[i].r; len[i] = abs(Seg[i].l - Seg[i].r); sum += len[i]; if(Seg[i].r < Seg[i].l) swap(Seg[i].l, Seg[i].r); } int minr = INT_MAX, maxl = 0; for(int i = 1; i <= n; i++) { auto [l, r] = Seg[i]; if(minr > r) { minr = r; // maxrlen = len[i]; } } for(int i = 1; i <= n; i++) { auto [l, r] = Seg[i]; if(maxl < l) { maxl = l; // maxllen = len[i]; } } // cout << maxrlen << ' ' << maxllen << ' ' << maxl << ' ' << minr << endl; if(maxl >= minr) cout << sum + 2 * (maxl - minr) << endl; else cout << sum << endl; } return 0; }