P14562 宇宙 题解

· · 题解

想要让第 i 维不被黑洞吞噬，就要将它加要 x+1，所以如果大于 x+1 就不用增加，否则就要用 x+1-v_i 步。所以不难得到：

\sum_{i=1}^n \max(x+1-v_i,0)\le xk

我们对 v 进行排序，显然前面一段是取 x+1-v_i，后面一段是取 0。设有一个最大的 j 满足 v_j\le x+1，可以变化成：

\sum_{i=1}^j x+1-v_i\le xk $j(x+1)-sv_j\le xk x\le \cfrac{sv_j-j}{j-k}

因为 x 取最大值所以 x=\cfrac{sv_j-j}{j-k}。

这里的 j 可以用双指针维护，所以讨论 j+1 时 v_{j+1}\le x+1 的合法性。

v_{j+1}\le\cfrac{sv_j-j}{j-k}+1 (j-k)v_{j+1}\le sv_j-k

注意因为有 j-k 的乘除移项所以要考虑 j\ge k。

代码中 i 就是 k 的意思。

#include<bits/stdc++.h>

using namespace std;

const int N = 1e6 + 5;

long long c, n, j, v[N];

int main()
{
    cin >> c >> n;
    for (int i = 1; i <= n; i ++ ) scanf("%lld", &v[i]);
    sort(v + 1, v + n + 1);
    for (int i = 1; i <= n; i ++ ) v[i] += v[i - 1];
    for (int i = 1; i < n; i ++ )
    {
        while (j < i || j < n && v[j] - i >= (v[j + 1] - v[j]) * (j - i)) j ++ ;
        printf("%lld ", (v[j] - j) / (j - i));
    }
    return 0;
}