A175447.[CSP-S 2026] 能量水晶 / CRYSTAL 题解
题目大意与数据范围\COLOR{GREEN}题目大意与数据范围题目大意与数据范围
给定长度为 nnn 的整数数组。一次操作可以把任意一个数加 1,同一个数可以操作多次。最多操作 mmm 次,求最终最多有多少个数相等。
完整数据:1≤n≤5×105, 0≤m≤1018, ∣ai∣≤10121 \le n \le 5 \times 10^5,\ 0 \le m \le 10^{18},\ |a_i| \le 10^{12}1≤n≤5×105, 0≤m≤1018, ∣ai ∣≤1012。没有多组测试。
先强调两个条件:只能增加,不能减少;操作次数是至多,不必用完。
暴力思路\COLOR{GREEN}{暴力思路}暴力思路
1. 输入A数组并 升序排序!!\COLOR{RED}{升序排序!!}升序排序!!
2. 枚举每个AIA_IAI ,向前遍历AJ(J≤I−1)A_J(J \LE I-1)AJ (J≤I−1),当前代价SUM=SUM+(AI−AJ)SUM=SUM+(A_I-A_J)SUM=SUM+(AI −AJ )。如果SUM≤MSUM \LE MSUM≤M,则当前元素数CNT=CNT+1CNT=CNT+1CNT=CNT+1,否则结束循环,DPI=CNTDP_I=CNTDPI =CNT
3. 枚举每个DPIDP_IDPI ,取最大值输出
代码如下
时间复杂度:O(n2)\boldsymbol{O(n^2)}O(n2)
预计得分:45pts45 pts45pts
正解思路\COLOR{GREEN}{正解思路}正解思路
1. 输入A数组并 升序排序!!\COLOR{RED}{升序排序!!}升序排序!!
2. 对A数组进行前缀和SUM!!\COLOR{RED}{前缀和SUM!!}前缀和SUM!!
3. 枚举每个AIA_IAI ,令L=1,R=I−1L=1,R=I-1L=1,R=I−1,向前二分AMID(MID=L+R2≤I−1)A_{MID}(MID=\FRAC{L+R}{2}\LE I-1)AMID (MID=2L+R ≤I−1),当前代价SUM0=AI∗(I−MID)−(SUMI−1−SUMMID−1)SUM0=A_I*(I-MID)-(SUM_{I-1}-SUM_{MID-1})SUM0=AI ∗(I−MID)−(SUMI−1 −SUMMID−1 )。如果SUM≤MSUM \LE
MSUM≤M,则R=MID−1R=MID-1R=MID−1,否则L=MID+1L=MID+1L=MID+1,当L>RL>RL>R,则DPI=I−L+1DP_I=I-L+1DPI =I−L+1
4. 枚举每个DPIDP_IDPI ,取最大值输出
代码如下
时间复杂度:O(nlogn)\boldsymbol{O(n \log n)}O(nlogn)
预计得分:100pts100 pts100pts
最后
祝大家CSP取得不错的成绩🎉🎉🎉