题目链接https://ac.nowcoder.com/acm/contest/136617/J题目大意给你一个初始数组和一个目标数组你可以对非最大值1、对非最小值-1问能否以及最少几步实现转化。具体来说你有两个长度均为N的整数序列A初始和B目标。你可以对A重复执行以下两种操作选一个不是当前数组最大值的元素把它1。选一个不是当前数组最小值的元素把它-1。每次操作代价为1。你需要判断能否把A变成B并求出最小操作次数如果不可能输出-1。题目思路这道题的核心是极值约束下的最小操作数问题。关键在于最大值不能升、最小值不能降因此目标极值必须落在初始极值范围内否则无解。在满足该条件下每个元素理论上可以独立移动到目标值总步数为所有 |a[i]-b[i]| 之和。唯一例外是n2时两个元素恰好要互换一个从最大值变最小值另一个从最小值变最大值会形成死锁若 n≥3则可选第三个元素作为“垫子”临时充当前极值来解锁此时只需在总和上加上该垫子绕路相比直达的最小额外代价。其他所有情况包括多极值均可直接输出总和。代码如下#include bits/stdc.h using namespace std; using i128 __int128; #define int long long #define endl \n const int N 4e5 10; int n; int a[N], b[N]; int sum; void solve() { cin n; sum 0; //初始化极值 int amx -1e9 - 1, amn 1e9 1; for (int i 1; i n;i){ cin a[i]; amx max(amx, a[i]); amn min(amn, a[i]); } int bmx -1e9 - 1, bmn 1e9 1; for (int i 1; i n;i){ cin b[i]; bmx max(bmx, b[i]); bmn min(bmn, b[i]); } //1.可行性判断目标极值不能超过初始极值范围 if(amxbmx||amnbmn){ cout -1 endl; return; } //2.强制截断a[i]到[bmn,bmx]范围内累计基础代价 for (int i 1; i n;i){ if(a[i]bmx){ sum a[i] - bmx; a[i] bmx; } if(a[i]bmn){ sum bmn - a[i]; a[i] bmn; } } //3.如果目标值全部相同直接输出此时所有a[i]已被截断到该值 if(bmxbmn){ //但注意如果目标全相等sum已经是截断代价还需要加上到目标值的差值 //但截断后a[i]已经等于bmx所以差值为0直接输出即可 cout sum endl; return; } //4.统计互换配对 int cnt1 0, cnt2 0; int i1 0, i2 0; for (int i 1; i n;i){ if(a[i]bmxb[i]bmn){ cnt1; i1 i; } if(a[i]bmnb[i]bmx){ cnt2; i2 i; } //累计每个点从截断后到目标值的代价 sum abs(a[i] - b[i]); } //5.处理唯一的互换死锁 if(cnt11cnt21){ if(n2){ cout -1 endl; return; } //n3,找到一个‘垫子’点计算最小额外代价 int extra LLONG_MAX; for (int i 1; i n;i){ if(ii1||ii2){ continue; } //直达代价 int direct abs(a[i] - b[i]); // 垫子先走到bmx再走到自己目标b[i]; int cost_to_bmx abs(a[i] - bmx) abs(bmx - b[i]); // 垫子先走到bmN再走到自己目标b[i]; int cost_to_bmn abs(a[i] - bmn) abs(bmn - b[i]); //额外代价绕路总代价-直达代价 int cur_extra min(cost_to_bmx - direct, cost_to_bmn - direct); extra min(extra, cur_extra); } // 理论上n3一定能找到垫子extra必定有效 sum extra; cout sum endl; return; } //6.其他所有情况直接输出即可 cout sum endl; } signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { solve(); } return 0; }