自动搬运

查看原文

来自洛谷，原作者为

	lqs NOIP 2025 rp++！

搬运于2025-08-24 22:50:34，当前版本为作者最后更新于2023-09-29 18:35:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

和 lyt 组队随便打了打。

翻译：给定 $n$ 个数，现在你需要从中任意删除 $m$ 个数，然后对剩余 $n-m$ 个数进行以下操作：

• 将 $a_{i}$ 加上 $1$。

• 将 $a_{i}$ 减去 $1$。

• 将 $a_{i}$ 除以 $2$。

每次操作代价为 $1$，而且在操作过程中你不能把 $a_{i}$ 变为 $0$。问把剩余的数变成相同的数的最小代价是多少。

• 数据范围：多测 $1 \le T \le 10$，$1 \le m < n \le 500$，$1 \le a_{i} \le 10^9$。

首先发现 $n \le 500$ 与 $6$ 秒的实现，考虑三次方做法。

但按照题目的意思枚举删哪些点肯定行不通。于是我们考虑枚举最终变成的那个值，然后计算所有点变成那个值的代价，删掉最大的 $m$ 个点，剩余点代价之和取最小值。

但是值域有 $10^9$，因此我们考虑答案可能在哪些点。

容易猜答案存在于某个数不断除以 $2$ 的某个结果中，因此存下每个数不断除以 $2$ 直到 $1$ 的所有结果，枚举它，再按上面的方法统计最小值即可。

于是我们惊人的发现 AC 了。复杂度是 $O(Tn^2 \log^2 V)$ 的。第一只 $\log$ 是枚举答案的，第二只 $\log$ 是对于 $i \in [1,n]$ 计算 $a_{i}$ 的代价的，$V$ 是值域。

• 现在我们考虑证明。

我们只需证明答案不在除以 $k$ 后存在加 $1$ 减 $1$ 之类的答案即可。那么这个证明类似一个经典问题：给定 $n$ 个坐标，要求你再另外选出一个坐标，要求所有点到此坐标距离最短。

显然，在这个问题中，若 $n$ 为奇数，答案为排序后的中间点；若 $n$ 为偶数，答案为排序后两个中间点其中一个。

为什么不会是中间点加减 $1$ 呢？对于奇数显然会有一半加 $1$ 个点贡献多 $1$，显然更劣；对于偶数，答案不变。

因此原问题类比这个问题可得答案一定在除以 $k$ 的某个关键点上。

code：

#include<bits/stdc++.h>
using namespace std;
#define N 505
#define int long long
int n,m,i,j,ans,a[N],t,s[N];
vector<int>G;
signed main(){
	scanf("%lld",&t);
	while(t--){
		G.clear();
		scanf("%lld%lld",&n,&m),ans=1e9;
		for(i=1;i<=n;i++) scanf("%lld",&a[i]);
		for(i=1;i<=n;i++){
			int k=a[i];
			while(k){
				G.push_back(k);
				k>>=1;
			}
		}
		for(int y:G){
			for(i=1;i<=n;i++) s[i]=1e9;
			for(i=1;i<=n;i++){
				int k=a[i],cnt=0;
				while(k>=1){
					s[i]=min(s[i],cnt+abs(k-y));
					k>>=1,cnt++;
				}
			}
			sort(s+1,s+1+n);
			int sum=0;
			for(i=1;i<=n-m;i++) sum+=s[i];
			ans=min(ans,sum);
		}
		printf("%lld\n",ans);
	}
	return 0;
}