P7382 题解

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

• 完结撒花~