[ICPC2022 Jinan R] Tower

· · 题解

和 lyt 组队随便打了打。

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

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

首先发现 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;
}