P7382 题解

发表于 2023-09-03

简单数学题

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

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

然后我们考虑，要从其中选出 $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;
}