P17831 [CSP-S 2026] 能量水晶 / crystal（官方数据）

/* MD / 富文本中的 .toc（含博客园搬家等嵌套结构）；.toc-box 在侧栏，不受影响 */
#content_views .toc,
/* 编辑器常在目录前后插入空 p（:empty 仍占 20px），一并去掉避免顶空隙 */
#content_views.markdown_views > p:empty:has(+ .toc),
#content_views.markdown_views > .toc + p:empty,
/* 富文本旧版目录标记 */
#content_views.htmledit_views #main-toc,
#content_views.htmledit_views #hr-toc,
#content_views.htmledit_views p[id*=\”-toc\”] {
display: none !important;
}
/* 目录去掉后，紧跟的首个标题不再多出一块上边距 */
#content_views.markdown_views > .toc + h1,
#content_views.markdown_views > .toc + h2,
#content_views.markdown_views > .toc + h3,
#content_views.markdown_views > .toc + h4,
#content_views.markdown_views > .toc + p:empty + h1,
#content_views.markdown_views > .toc + p:empty + h2,
#content_views.markdown_views > .toc + p:empty + h3,
#content_views.markdown_views > .toc + p:empty + h4 {
margin-top: 0 !important;
}

题目描述

小 R 有 n 颗能量水晶，其中第 i (1≤i≤n) 颗的能量值为整数 ai​。

小 R 想用其中若干颗能量水晶合成一颗大水晶，用于合成的水晶必须具有相同的能量值。小 R 希望参与合成的水晶尽可能多。他可以进行至多 m 次操作。每次操作可以任选一颗水晶，将其能量值增加 1；同一颗水晶可以被重复选择。

你需要帮助小 R 求出，进行至多 m 次操作后，他最多能用多少颗能量水晶合成一颗大水晶。

输入格式

从文件 crystal.in 中读入数据。

输入的第一行包含一个正整数 n 和一个非负整数 m，分别表示能量水晶的数量和最多可以进行的操作次数。

输入的第二行包含 n 个整数 a1​,a2​,…,an​，依次表示每颗能量水晶的能量值。

输出格式

输出到文件 crystal.out 中。

输出一行一个正整数，表示进行至多 m 次操作后，小 R 最多能用多少颗能量水晶合成一颗大水晶。

输入输出样例

输入 #1复制

5 5
1 2 4 8 9

输出 #1复制

3

输入 #2复制

5 8
-3 -1 2 2 7

输出 #2复制

4

说明/提示

样例 1 解释

小 R 有 5 颗能量水晶，能量值分别为 1,2,4,8,9。他可以对能量值为 1 和 2 的水晶分别操作 3 次和 2 次，使原来能量值为 1,2,4 的三颗水晶的能量值都变成 4，共进行 5 次操作。因此小 R 可以用 3 颗能量水晶合成一颗大水晶。

样例 3

见题目目录下的 crystal/3.in 与 crystal/3.ans。

该样例满足测试点 8,9 的约束条件。

样例 4

见题目目录下的 crystal/4.in 与 crystal/4.ans。

该样例满足测试点 10∼12 的约束条件。

数据范围

对于所有测试数据，均有：

• 1≤n≤5×105，0≤m≤1018；
• 对于所有 i (1≤i≤n)，均有 ∣ai​∣≤1012。

特殊性质 A：对于所有 i (1≤i≤n)，均有 ai​=i。

特殊性质 B：a1​,a2​,…,an​ 构成等差数列。

思路：

枚举+二分+前缀和优化时间

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[500005],ans=-1123456789098,d[500005];
bool check(int x,int t){
int z=a[t]*(t-x+1);
int k=d[t]-d[x-1];
return k+m>=z;
}
int solve(int x){
int l=1,r=x;
while(l<r){
int mid=(l+r)/2;
if(check(mid,x)){
r=mid;
}
else{
l=mid+1;
}
}
return x-l+1;
}
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+1+n);
for(int i=1;i<=n;i++){
d[i]=d[i-1]+a[i];
}
for(int i=1;i<=n;i++){
ans=max(ans,solve(i));
}
cout<<ans;
return 0;
}