P7382 题解

感觉挺奇妙的一道题，思路很巧。

先构造一个数组是给出两个数组的差，再排序，这一点不用多说。

然后我们考虑，要从其中选出 \(K\) 个元素修改，那这 \(K\) 个元素一定是排序后的数组中两端的元素。

既然这样，那剩下的 \(n-K\) 个元素一定是新数组中连续的一段。

于是问题就变成了，在一段数中选择一个数 \(x\)，使得 \[ \sum_{i=1}^N |A_i-x|\]

最小。由小学奥数得知，这个数应该是这组数的中位数。

至于知道了中位数如何 \(O(1)\) 的计算答案，另一篇题解已经讲的很清楚了。

放代码： ``` #include <bits/stdc++.h> #define int long long using namespace std; int a[100005],b[100005],cha[100005],n,k,sum[100005],ans,inf=0x3f3f3f3f3f3f3f3f; signed main(){ cin>>n>>k; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)cin>>b[i],cha[i]=a[i]-b[i]; sort(cha+1,cha+n+1); for(int i=1;i<=n;i++)sum[i]=sum[i-1]+cha[i]; k=n-k,ans=inf; for(int i=1;i+k-1<=n;i++){ int r=i+k-1; int mid=(i+r)>>1; int now=cha[mid](mid-i+1)-(sum[mid]-sum[i-1])+(sum[r]-sum[mid])-cha[mid](r-mid); ans=min(ans,now); } cout<<ans; return 0; }