I. 加减

可以借助二分做.

易得:经过操作之后,出现次数最多的数一定是原来数组中的数.

数的顺序对于答案没有影响,不妨先排序.

然后就可以枚举原来数组中的数,使用给定操作去取得最优解,然后所有可能中的最大值即为答案.

假设当前枚举到的数为.

贪心地优先取和的差的绝对值小的数是最优解之一.

然后就可以二分差值,找到满足可以取完所有和的差值在以内的数,最大的.由于之前已经排序了,所以满足条件的数就是原数组的一段连续子数组,通过二分可以找到边界,通过前缀和可以快速计算代价.

然后差值为的数可能可以取一部分,可能一个也取不了,也有可能不存在,前两个情况根据剩余代价去判断就可以了,不存在的情况也是再加个特判.

AC代码

#include <bits/stdc++.h>
using namespace std;
#ifdef BACKLIGHT
#include "debug.h"
#else
#define debug(...)
#endif

const int N = 1e5 + 5;

int n, a[N];
int64_t k, s[N];
map<int, int> cnt;
int R(int p, int d) { return upper_bound(a + 1, a + 1 + n, a[p] + d) - a - 1; }
int L(int p, int d) { return lower_bound(a + 1, a + 1 + n, a[p] - d) - a; }
int64_t getCost(int p, int d) {
  int rp = R(p, d);
  int lp = L(p, d);
  int64_t cost = 0;
  cost += (int64_t(p - lp + 1) * a[p]) - (s[p] - s[lp - 1]);
  cost += (s[rp] - s[p - 1]) - ((int64_t(rp - p + 1) * a[p]));
  return cost;
}
int calc(int p) {
  int l = 0, r = 1e9, mid, d = 0;
  while (l <= r) {
    mid = (l + r) >> 1;
    if (getCost(p, mid) <= k)
      l = mid + 1, d = mid;
    else
      r = mid - 1;
  }
  int64_t cost = getCost(p, d);
  l = L(p, d);
  r = R(p, d);
  return (r - l + 1) + min(int64_t(cnt[a[p] - d - 1] + cnt[a[p] + d + 1]), (k - cost) / (d + 1));
}
void solve(int Case) {
  scanf("%d %lld", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), ++cnt[a[i]];
  sort(a + 1, a + 1 + n);
  for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + a[i];
  int ans = 0;
  for (int i = 1; i <= n; ++i) ans = max(ans, calc(i));
  printf("%d\n", ans);
}

int main() {
#ifdef BACKLIGHT
  freopen("a.in", "r", stdin);
#endif
  int T = 1;
  // scanf("%d", &T);
  for (int t = 1; t <= T; ++t) solve(t);
  return 0;
}