操作数组【牛客tracker 每日一题】

操作数组

时间限制：1秒 空间限制：256M

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

给定两个长度为n nn的数组a aa和b bb((下标从1 11开始))，你的目标是使a = b a=ba=b，为了完成你的目标，你可以执行以下操作任意次（也可以是0 00次）：

• 选择两个正整数i , j i,ji,j，满足1 ≤ i , j ≤ n 1≤i,j≤n1≤i,j≤n且i ii≠j jj，使a i a_iai​变成a i − 1 a_i−1ai​−1，a j a_jaj​变成a j + 1 a_j+1aj​+1。

尽管你可以执行任意次操作，但这里求的是最小操作次数。如果无论如何都不能使a = b a=ba=b，请报告。

输入描述：

第一行包含一个正整数n ( 2 ≤ n ≤ 10 5 ) n (2≤n≤10^5)n(2≤n≤105)，n nn表示数组的长度。

第二行包含n nn个正整数a 1 , a 2 , … , a n ( 1 ≤ a i ≤ 10 9 ) a_1,a_2,…,a_n (1≤a_i≤10^9)a1​,a2​,…,an​(1≤ai​≤109)。

第三行包含n nn个正整数b 1 , b 2 , … , b n ( 1 ≤ b i ≤ 10 9 ) b_1,b_2,…,b_n (1≤b_i≤10^9)b1​,b2​,…,bn​(1≤bi​≤109)。

输出描述：

输出包含一个整数，表示最小操作次数。如果无论如何都不能使a = b a=ba=b，输出− 1 −1−1。

示例1

输入：

4 1 2 3 4 4 3 2 1

输出：

4

解题思路

本题核心是操作本质转化+可行性判断+极简计数，高效求解最小操作次数。首先分析操作特性：每次操作仅将1 11个数值单位从一个位置转移到另一个位置，数组总和始终保持不变，因此首先判断数组a和b的总和是否相等，不相等则直接输出-1。随后计算每个位置的差值d[i] = b[i] - a[i]，正差值代表该位置需要接收的单位数，负差值代表需要移出的单位数。由于一次操作恰好完成1 11个单位的转移，因此最小操作次数等于所有正差值的累加和，该方法时间复杂度为O(n)，简洁高效地适配题目数据规模。

总结

核心逻辑：操作等价于数值单位的转移，数组总和相等是可行的前提，最小操作次数=总转移单位数。
关键操作：数组总和校验、位置差值计算、正差值累加求和。
效率保障：线性时间复杂度，无冗余计算，完美适配n≤1e5的大数据范围。

代码内容

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll p=1e9+7;constll INF=1e18;constll M=1e6+10;intmain(){ios::sync_with_stdio(false);cin.tie(0);ll n;cin>>n;vector<ll>a(n+1),b(n+1);for(ll i=1;i<=n;++i)cin>>a[i];vector<ll>z,f;ll s=0;for(ll i=1;i<=n;++i){cin>>b[i];ll d=b[i]-a[i];if(d<0)f.push_back(d);elseif(d>0)z.push_back(d);s+=d;}if(s!=0){cout<<"-1\n";return0;}sort(z.begin(),z.end(),greater<ll>());sort(f.begin(),f.end());ll ans=0,i=0,j=0;while(i<(ll)z.size()&&j<(ll)f.size()){if(z[i]>-f[j]){ans+=-f[j];z[i]+=f[j];f[j]=0;++j;}elseif(z[i]<-f[j]){ans+=z[i];f[j]+=z[i];z[i]=0;++i;}else{ans+=z[i];f[j]=0;z[i]=0;++i;++j;}}if(i!=(ll)z.size()||j!=(ll)f.size())cout<<"-1\n";elsecout<<ans<<'\n';return0;}