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

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

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

思路

要想让前

k

小和最大，必需让第

k

小最大。

证明

~~显然。~~

如果我们使第

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

比较，若小则不合法，若刚好等于那正好，若大了我们可以调整到刚好合适。

如何调整

把同一个

a_i

拆出的两个第

k

小值合到一个罐子里存储。每次进行这种操作减小

1

个，一定可以调整成功。

代码

CPP

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

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

文章操作

思路

相关推荐

评论

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