题解：P14562 宇宙

· · 题解

P14562 宇宙

题目传送门

思路

被 TLE 创死了。

对 u_j 升序排序后，设前 m 个元素满足 u_j \le x，则求和式可表示为 m\cdot x - \sum_{j=1}^m u_j。用前缀和算该值，用双指针找到每个 k 对应的最优 m。

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

时间复杂度为 \mathcal{O}(n \log n)。 :::success[Code]

#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;
}

:::