P14562 宇宙

思路

~~被 TLE 创死了。~~

对

u_j

升序排序后，设前

m

个元素满足

u_j \le x

，则求和式可表示为

m\cdot x - \sum_{j=1}^m u_j

。用前缀和算该值，用双指针找到每个

k

对应的最优

m

。

将 $v_j$ 转换为 $u_j = v_j - 1$ ，并对 $u_j$ 升序排序。
对于前缀和数组 $S$ ，其中 $S[m] = \sum_{j=1}^m u_j$ 。
对每个 $k$ ，用双指针维护最优的 $m$ ，使得 $\frac{S[m]}{m-k}$ 最小（对应最大的 $x$ ），最终 $x = \lfloor \frac{S[m]}{m-k} \rfloor$ 即可。

时间复杂度为

\mathcal{O}(n \log n)

。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
#define int __int128
constexpr int N = 78787878;
int arr1[N], arr2[N], arr3[N], ans[N], n, m, sum = 2;
void write(int x){
    if(x == 0) return;
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x / 10) write(x / 10);
    putchar(x % 10 + '0');
}
int read(){
    int x = 0;
    char ch = getchar();
    while(ch < '0' || ch > '9') ch = getchar();
    while(ch >= '0' && ch <= '9'){
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x;
}
signed main(){
    n = read(), m = read();
    int nn = m, mm = n;
    for(int i = 0; i < nn; i++){
        int x;
        x = read();
        arr1[i] = x;
        arr2[i] = arr1[i] - 1;
    }
    sort(arr2, arr2 + nn);
    arr3[0] = 0;
    for(int i = 1; i <= nn; i++) arr3[i] = arr3[i - 1] + arr2[i - 1];
    for(int k = 1; k <= nn - 1; k++){
        sum = max(sum, (k + 1));
        while(sum < nn){
            int t1 = sum - k;
            int t2 = (sum + 1) - k;
            int a = arr3[sum] * t2;
            int b = arr3[sum + 1] * t1;
            if(a > b){
                sum++;
            }else{
                break;
            }
        }
        int t = sum - k;
        ans[k - 1] = arr3[sum] / t;
    }
    for(int i = 0; i < nn - 1; i++){
        if(ans[i] == 0) putchar('0');
        else write(ans[i]);
        if(i != nn - 2) putchar(' ');
        else putchar('\n');
    }
    return 0;
}

题解：P14562 宇宙

文章操作

P14562 宇宙

思路

相关推荐

评论

题解：P14562 宇宙