题解：B4427 [CSP-X2025 山东] 能量水晶

· · 题解

CSP-X 重现赛中打到的挺有趣的一题，可惜赛时挂分了。感觉 -X 出的比 -J 好。

题意就不说了，没看题意不建议直接看题解。

思路

要想让前 k 小和最大，必需让第 k 小最大。

:::success[证明]

显然。

如果我们使第 k 小没有取到最大值，则一定可以在保证前 k-1 小不变的前提下使第 k 小变大，这样操作后前 k 小的数的总和一定变大。

:::

得到这个结论后考虑如何求出第 k 小的最大值。由于 a_i 范围较小，考虑直接枚举。

如何判断一个第 k 小数的值是否合法？如下图。

\left\{\begin{matrix} \color{blue}{1} & \texttt{ — } & \color{orange}{1} & & \\ \color{blue}{3} & \texttt{ — } & 3 & & \\ \color{blue}{5} & \texttt{ — } & 3 & \color{orange}{2} & \\ \color{blue}{7} & \texttt{ — } & 3 & 3 & \color{orange}{1}\\ \color{blue}{9} & \texttt{ — } & 3 & 3 & 3\end{matrix}\right.

当前试的第 k 小值为 3 。我们把每个数都拆成若干 3 和余数形式。我们先不去管 m 的限制，则除前 k-1 小的罐子我们不管外，我们最多装 7 个罐子，即 m-k+1 的最大值为 7 。

算法到这里已经很明确了，我们求出可以构造的 m-k+1 的最大值，与题目给出的 m-k+1 比较，若小则不合法，若刚好等于那正好，若大了我们可以调整到刚好合适。

:::info[如何调整]

把同一个 a_i 拆出的两个第 k 小值合到一个罐子里存储。每次进行这种操作减小 1 个，一定可以调整成功。

:::

:::success[代码]{open}

#include<bits/stdc++.h>
#define int long long
#define double long double
#define fi first
#define se second
#define pii pair<int,int>
#define endl '\n'
using namespace std;
const int N=2e3+10;
int n;
int m,k;
int a[N];
int mx;
int ans;
signed main(){
//  freopen("energy.in","r",stdin);
//  freopen("energy.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        mx=max(mx,a[i]);
    }
    for(int asd=1;asd<=mx;asd++){//枚举第 $ k $ 小  
        const int x=asd;
        priority_queue<int>pq;//用于算答案 
        int cnt=0;
        for(int i=1;i<=n;i++){
            cnt+=a[i]/x;
            if(a[i]%x){
                pq.push(a[i]%x);
            }
        }
        cnt-=m-k;
        if(cnt<=0){//不合法直接continue 
            continue;
        }
        cnt=min(cnt,k);
        int sum=cnt*x;
        for(int i=1;i<=k-cnt;i++){
            if(pq.empty()){//前k-1小凑不齐也不合法 
                sum=-1;
                break;
            }
            sum+=pq.top();
            pq.pop();
        }
        if(sum==-1){
            continue;
        }
        ans=max(ans,sum);
    }
    if(k>=n){//特判 
        int sum=0;
        for(int i=1;i<=n;i++){
            sum+=a[i];
        }
        ans=max(ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}

:::