CSP-S 2026 A题 能量水晶 题解（6个解法）

零、背景

之前已经分享了历年 CSP-J/S 的比赛题解。
今天开始，分享 CSP-S 2026 比赛题解。

为了避免四道题放在一篇导致文章过长，我计划每道题单独写一篇，最后再给出一个总结。

这篇文章分享 CSP-S 2026 第一道题「能量水晶 crystal」的题解。

PS：pdf 题目和源码已经上传网盘，后台回复 CSP-S-2026 获取题目与源码。

一、题目

小 R 有 n 颗能量水晶，第 i 颗水晶的能量值为整数 a_i。
每次操作可以任选一颗水晶，将它的能量值增加 1，同一颗水晶可以被重复选择。

小 R 一共可以进行至多 m 次操作。
小 R 想用其中若干颗能量水晶合成一颗大水晶，参与合成的水晶必须具有相同的能量值。

问进行至多 m 次操作后，最多能用多少颗水晶合成大水晶。

二、算法分析

答案求最大值，数据范围又是 5 × 10^5，显然需要 O(n log n) 的解法或者更快的解法。

先想清楚一个最基础的问题：最终相同的能量值取多少，以及优先选哪些水晶。

假设最终相同的能量值是第 R 个水晶，值为 nums[R]。
显然，每次操作都需要优先选择小于等于且最接近 nums[R] 的水晶，不断加一，直到把它的能量值增加到 nums[R]。
这样需要加的次数最少，参与合成的水晶才能尽量多。

怎么找到小于等于且最接近 nums[R] 的水晶？
预处理水晶，排序后，上一个水晶就是小于等于且最接近 nums[R] 的水晶。
所以最优方案中，选中的水晶是排序后的一段连续区间 [L, R]，最终值就是 nums[R]。

因此问题转化为：枚举右端点 R，找到最长的合法区间 [L, R]。

三、解法一：暴力枚举（50 分）

思路：对于每个右边界 R，从大到小枚举左边界 L，不断把 nums[L] 的值增加到 nums[R]，判断操作次数是否超过 m。
复杂度：O(n^2)。

前 9 个测试点 n ≤ 5000 可以轻松通过；
从第 10 个测试点起 n = 5 × 10^5 必然超时。
第 13 个测试点意外通过，累计通过 10 个测试点。
所以这个做法拿到 50 分。

核心代码如下：

ll SolverOne(const ll R) {  //
  ll l = R;  // (l, R]
  ll left = m;
  while (l >= 0) {
    left -= nums[R] - nums[l];
    if (left < 0) break;
    l--;
  }
  return R - l;
}

四、解法二：去重优化（80 分）

思路：第 10~12 组测试用例的值域不超过 100，这意味着有很多相同值。
如果最终能量值为 nums[R]，显然所有值为 nums[R] 的水晶都需要选择，所以相同值只需要枚举最后一个位置。
复杂度：O(100 * n)。
得分：80分

核心代码如下：

ll ans = 0;
for (int i = 0; i < n; i++) {
   // 相同值只枚举最后一个
  if (i + 1 < n && nums[i] == nums[i + 1]) continue; 
  ans = max(ans, SolverForce(i));
}
printf("%lld\n", ans);

右端点确定后，向前枚举左边界时也可以去重。

先预处理每个值第一次出现的位置 unordered_map<ll, int> firstPos。
枚举一个 L 时，根据当前值的个数判断能否全部覆盖；
能全部覆盖时，一次性把这些位置全部处理掉；
不能全部覆盖时，再往前的位置都无法覆盖，直接结束。

复杂度：去重后 O(diff^2)，其中 diff 为不同值的个数。
最终这个做法还是拿到 80 分。

核心代码如下：

firstPos.clear();
for (int i = n - 1; i >= 0; i--) {
  firstPos[nums[i]] = i;  // 每个值第一次出现的位置
}

ll SolverForce(const ll R) {  //
  ll l = R;  // (l, R]
  ll left = m;
  while (l >= 0 && left >= nums[R] - nums[l]) {
    // 与右端点同值，无需花费
    if (nums[R] == nums[l]) {  
      l--;
      continue;
    }
    // 值为 nums[l] 剩余的个数
    ll minLeft = firstPos[nums[l]];
    // 看 left 可以覆盖几个 nums[l]
    ll maxCover = left / (nums[R] - nums[l]);
    // 已经保证至少覆盖一个
    ll cover = min(maxCover, l - minLeft + 1);
    left -= cover * (nums[R] - nums[l]);
    l -= cover;
  }
  return R - l;
}

五、解法三：性质 A 优化（90 分）

思路：第 13~15 组测试数据满足特殊性质 A，所有数字连续递增（a_i = i）。

确定右端点 R 后，从右往左第一个水晶增加 0，第二个增加 1，第三个增加 2，依次递推。

令 x = R - L，总共增加 m。
可以解方程 (0 + x) * (x + 1) / 2 <= m。
直接得到 L = R - x。
复杂度：O(n)。
得分：90分
最终前 15 组与 18~20 组测试数据全部通过，共 18 组，拿到 90 分。

核心代码如下：

ll SolverA(ll R) {
  // 0 + 1 + 2 + ... + (R-L)
  // 令 x = R - L
  // (0 + x) * (x+1) / 2 <= m
  // x^2 + x - 2m <= 0
  // x <= (sqrt(1 + 8m) - 1) / 2

  ll x = (sqrt(1 + 8 * m) - 1) / 2;
  ll L = max(R - x, 0ll);
  return R - L + 1;
}

其实性质 A 中我们不关心具体值，只关心与枚举值的相对值。

枚举值的起始相对值都是 0，只是越往后 R - L 越大。
所以枚举到最后一个位置时 R - L 最大。

故直接计算最后一个位置的答案即可，复杂度 O(1)。

核心代码如下：

if (isPropertyA) {
  printf("%lld\n", SolverA(n - 1));
  return;
}

六、解法四：性质 B 优化（100 分）

思路：第 16~18 组测试数据满足特殊性质 B，所有数字形成等差数列，公差为 d。

可以套用性质 A 的解法，只是方程更复杂：(0 + xd) * (1 + x) / 2 <= m。
解得 x <= (sqrt(d^2 + 8dm) - d) / (2d)，直接计算即可。
复杂度：O(1)。
这个做法有一组样例没过，拿到 95 分。

核心代码如下：

ll SolverB(ll R) {
  // 0 + d + 2d + ... + xd
  // (0+xd) * (1+x) / 2 <= m
  // x <= (sqrt(d^2+8dm) -d) / (2d)
  double dis = nums[1] - nums[0];  // 越界，存在精度问题
  ll x = (sqrt(dis * dis + 8 * dis * m) - dis) / (2 * dis);
  ll L = max(R - x, 0ll);
  return R - L + 1;
}

分析数据范围，m 和值域太大了，超过了 int64，double 计算存在精度问题。

不能解方程时，改用二分求方程的解。
判断条件还是 (0 + xd) * (1 + x) / 2 <= m，但全部用整数运算，避免精度问题。
复杂度：O(log n)。
得分： 100 分。

核心代码如下：

bool CheckB(ll mid, ll R) {
  ll rightAdd = 0;                  // 右端点自身无需增加
  ll leftAdd = nums[R] - nums[mid];
  ll len = R - mid + 1;
  return (rightAdd + leftAdd) * len / 2 <= m;
}
ll SolverB(ll R) {
  ll l = 0, r = R;  // [l, r]
  while (l < r) {
    ll mid = (l + r) / 2;
    if (CheckB(mid, R)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return R - r + 1;
}

七、解法五：前缀和 + 二分（100 分）

思路：对于第 R 个水晶，假设最多可以修改到第 L 个水晶。
既然解方程可以二分，那普通情况，是否可以二分查找左边界 L 呢？

可以发现，对于 [0, L) 都是不满足条件的，对于 [L, R] 都是满足条件的，满足单调性。
所以可以二分找到这个分界点 L，区间长度就是 R - L + 1。

那对于任意一个位置 L，如何快速判断是否满足条件呢？
可以利用前缀和，快速判断 [L, R] 需要加多少次才能使得所有值都等于 nums[R]。
公式也很简单：sum(L, R) + m >= (R - L + 1) * nums[R]

故可以二分快速找到边界 L。
复杂度：O(n log n)。

ll RangeSum(int l, int r) {
  if (l == 0) return preSum[r];
  return preSum[r] - preSum[l - 1];
}
bool Check(int L, int R) {
  ll k = R - L + 1;
  ll sum = RangeSum(L, R);
  return sum + m >= k * nums[R];
}
ll SolverOne(const ll R) {  //
  ll l = 0, r = R;  // [l, r]
  while (l < r) {
    ll mid = (l + r) / 2;
    if (Check(mid, R)) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return R - r + 1;
}

八、解法六：前缀和 + 双指针（100 分）

思路：继续分析对于每个 R，L 的规律，可以发现，L 是单调非递减的。
故可以使用一个左边界游标，复用上次的左边界，从而快速找到当前的左边界 L。
这种做法，一般称为双指针。

复杂度：
不考虑排序复杂度 O(n)。

int preL = 0;
ll SolverOne(const ll R) {  //
  while (preL <= R && !Check(preL, R)) {
    preL++;
  }
  return R - preL + 1;
}

九、总结

CSP-S 的第一道题难度比较简单。

即使没有想到二分，也可以根据合并相同值、性质A与性质B拿到尽可能多的人。

最暴力的做法，复杂度为 O(n^2)，得分 50 分。
根据相同值域的性质，可以把复杂度降到 O(diff^2)，得分 80分。
然后根据性质A，得分提到 90分。
最后再根据性质 B，得分提升到 95 分。

想到了二分之后，就会发现可以直接前缀和+二分来做，轻松拿到满分。
对于双指针，理解难度稍微大一些，不做要求。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号 ID：tiankonguse-code