自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:29:20，当前版本为作者最后更新于2022-09-01 16:39:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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;
}

• 完结撒花~