我居然没遇到一点困难？

A,B 数组差分排序，直接一个长为 n-k 的滑动窗口中位数扫过去就完事了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int a[N],b[N],d[N];
signed main()
{
	int n,k;cin>>n>>k;k=n-k;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)d[i]=b[i]-a[i];
	sort(d+1,d+n+1);
	int l=1,r=k,mid=(k+1)/2,sum1=0,sum2=0,ans=1e18;
	for(int i=1;i<=(k&1?mid-1:mid);i++)sum1+=d[i];
	for(int i=mid+1;i<=k;i++)sum2+=d[i];
	for(;r<=n;l++,r++,mid++)
	{
		ans=min(ans,sum2-sum1);
		sum1-=d[l],sum2-=d[mid+1];
		sum1+=d[(k&1?mid:mid+1)],sum2+=d[r+1];
	}
	cout<<ans;
	return 0;
}

• 前言：个人认为这道题挺有意思，是一道很不错的思维题。

Solution

• 考场上拿到这题,一眼看过去就注意到了高额的部分分，于是我们顺着 $k=0$ 的特殊情况入手：

• 当 $k=0$ 时，问题就转化为了求使得 $\sum_{i=1}^n{A_i-B_i+x}$ 取到最小值的整数 $x$ , 不难看出 $A_i-B_i$为一个定值，那么这就等价于给定直线上 $n$ 个点，另找一个点使它到所有点距离之和最小，这就是一道排序经典题型，不会的请转这儿。

• 考虑完特殊情况，我们来思考一下一般情况：令 $C_i=A_i-B_i$ ,这时我们发现如果将 $C$ 序列中每个数的看作一个点，那么题目的要求等价于让我们找一个点，使得给定 $C$ 序列中 $n$ 个点到其距离的前 $n-k$ 小距离之和最小。

• 由于答案与每个 $C_i$ 所在位置无关，所以我们可以将 $C$ 序列从小到大排序，这时有一个十分重要的结论：对于任意点 $x$ ,到其距离前 $n-k$ 小的点，一定是 $C$ 序列中连续的一段。

• 证明也比较容易，因为对于任意一个点 $x$ ,如果我们将其插入 $C$ 序列，那么到它距离前 $n-k$ 小的点，一定是从它开始，向左向右扩展，直到扩展满 $n-k$ 个。

• 那么此时我们就无需按 $x$ 来分类，而是按区间分类，对于 $C$ 序列中每一个长度为 $n-k$ 的子段，用 $k=0$ 的方法求出这一段的最小答案，最后再取最小值就行了，当然由于要快速求答案,所以还需要用前缀和优化一下，具体方法链接里有，就不详细阐述了。

• 代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N=1e5+10;
int n,k,X,A[N],B[N],delta[N];
LL res=LLONG_MAX,sum[N];
LL get(int L,int R)
{
      int mid=(L+R)>>1;
      if((R-L+1)&1)	return sum[R]-sum[mid]-sum[mid-1]+sum[L-1];
      else return sum[R]-sum[mid]-sum[mid]+sum[L-1];	
} 
int main()
{
      freopen("simfonija.in","r",stdin);
      freopen("simfonija.out","w",stdout);
      scanf("%d%d",&n,&k);
      for(int i=1;i<=n;i++)	scanf("%d",&A[i]);
      for(int i=1;i<=n;i++)	scanf("%d",&B[i]);
      for(int i=1;i<=n;i++)	delta[i]=A[i]-B[i];
      sort(delta+1,delta+n+1);
      for(int i=1;i<=n;i++)	sum[i]=sum[i-1]+delta[i];
      for(int i=1;i<=k+1;i++)	res=min(res,get(i,i+n-k-1)); 
      printf("%lld",res); 
      return 0;
}

• 完结撒花~