「Codeforces 1111B」Average Superhero Gang Power

题目链接

首先观察求平均数的公式

$$avg=\frac{sum}{n}$$

所以我们要么改变 $sum$ 要么改变 $n$

如果忽略 $k$ 这个条件，我们有以下解法

我们先删数，数量记为为 $q$ ，剩余数的和记为 $s'$

$$avg = \frac{s'+m-q}{n-q}$$

对于一个数，我们要么舍弃，要么保留，显然的我们需要先删小的数（可以用 Exchange Argument 证明

std::sort(a + 1, a + 1 + n, std::greater<int>());
double sum = 0, ans = 0;
rep(i, 1, n) {
    sum += a[i];
    int q = n - i;
    if (m >= q)
        ans = std::max(ans, (sum + m - q) / i)
}

现在我们加上 $k$ 这个条件，我们只需改动一行代码（因为 $k$ 的约束导致加上 $m-q$ 的目标不一定可以实现

ans = std::max(ans, (sum + std::min((m - q), i * k)) / i);

复杂度 $O(n)$

我也不知道我比赛时怎么想出 $O(n\log n)$ 的错误算法（划掉

此题需要注意溢出

#include <algorithm>
#include <iomanip>
#include <iostream>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;

ll a[100100];

int main() {
  std::ios::sync_with_stdio(false);
  cout.tie(0);
  ll n, k, m;
  cin >> n >> k >> m;
  double l, r;
  rep(i, 1, n) cin >> a[i];
  std::sort(a + 1, a + 1 + n, std::greater<int>());
  double sum = 0, ans = 0;
  rep(i, 1, n) {
    sum += a[i];
    if (m >= (n - i))
      ans = std::max(ans, (sum + std::min((m - (n - i)), i * k)) / i);
  }
  cout.setf(std::ios::fixed);
  cout << std::setprecision(14) << ans;
  return 0;
}