[CSP-S 2026] 能量水晶 题解
2026-11-07 09:26:55
发布于:浙江
17阅读
0回复
0点赞
A175447.[CSP-S 2026] 能量水晶 / crystal 题解
给定长度为 的整数数组。一次操作可以把任意一个数加 1,同一个数可以操作多次。最多操作 次,求最终最多有多少个数相等。
完整数据:。没有多组测试。
先强调两个条件:只能增加,不能减少;操作次数是至多,不必用完。
1. 输入a数组并
2. 枚举每个,向前遍历,当前代价。如果,则当前元素数,否则结束循环,
3. 枚举每个,取最大值输出
代码如下
#include<bits/stdc++.h>
using namespace std;
long long a[500005],dp[500005];
int main(){
// freopen("crystal.in","r",stdin);
// freopen("crystal.out","w",stdout);
int n;
long long m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}sort(a+1,a+1+n);
dp[1]=1;
for(int i=2;i<=n;i++){
int sum=0,cnt=1;
for(int j=i-1;j>=1;j--){
sum+=a[i]-a[j];
if(sum<=m){
cnt++;
}else{
break;
}
}dp[i]=cnt;
}long long ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,dp[i]);
}cout<<ans;
}
时间复杂度:
预计得分:
1. 输入a数组并
2. 对a数组进行
3. 枚举每个,令,向前二分,当前代价。如果,则,否则,当,则
4. 枚举每个,取最大值输出
代码如下
#include<bits/stdc++.h>
using namespace std;
long long a[500005],sum[500005],dp[500005];
int main(){
// freopen("crystal.in","r",stdin);
// freopen("crystal.out","w",stdout);
int n;
long long m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}sort(a+1,a+1+n);
dp[1]=1;
for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[i];
}for(int i=2;i<=n;i++){
if(m>=a[i]*(i-1)-sum[i-1]){
dp[i]=i;
}else{
int l=1,r=i-1;
while(l<=r){
int mid=(l+r)>>1;
if(a[i]*(i-mid)-(sum[i-1]-sum[mid-1])<=m){
r=mid-1;
}else{
l=mid+1;
}
}dp[i]=i-l+1;
}
}long long ans=0;
for(int i=1;i<=n;i++){
ans=max(ans,dp[i]);
}cout<<ans;
}
时间复杂度:
预计得分:
最后
祝大家CSP取得不错的成绩🎉🎉🎉
这里空空如也






有帮助,赞一个