思路分析

我们的目标是最大化 $\sum b_i$。由于 $b_i$ 的定义依赖于前缀 $MEX$，并且 $b_i$ 序列是非递减的（$b_1 \le b_2 \le ... \le b_n$），我们希望让 $b_i$ 的值尽可能早地、尽可能大地增长。

$b_i = MEX(\{a_1, ..., a_i\})$。为了让 $b_i$ 的值变大，我们需要让前缀 $\{a_1, ..., a_i\}$ 尽可能地包含从 $0$ 开始的连续整数。

• 为了最大化 $b_1 = MEX(\{a_1\})$，我们应该选择 $a_1=0$（如果数组 $a$ 中有 $0$ 的话）。这样 $b_1=1$。如果选择其他数， $b_1=0$。
• 为了最大化 $b_2 = MEX(\{a_1, a_2\})$，在 $a_1=0$ 的基础上，我们应该选择 $a_2=1$（如果数组 $a$ 中有 $1$ 的话）。这样 $\{a_1, a_2\} = \{0, 1\}$，使得 $b_2=2$。
• 以此类推，为了让 $b_i$ 达到最大可能值 $i$，我们需要让前缀 $\{a_1, ..., a_i\}$ 恰好是 $\{0, 1, ..., i-1\}$。

这启发我们采用一种贪心策略：按顺序构建重排后的数组 $a'$。在构建 $a'_i$ 时，我们优先选择能让 $MEX$ 值增大的数字。

设当前构建的前缀的 $MEX$ 值为 $m$。如果我们接下来放入数字 $m$，新的前缀的 $MEX$ 值就会大于等于 $m+1$。如果我们放入其他任何数字，新的 $MEX$ 值将仍然是 $m$。因此，在每一步，我们都应该优先使用我们拥有的、等于当前 $MEX$ 值的数字。

这个过程会形成一个最优的前缀 $0, 1, 2, ..., M-1$，其中 $M$ 是我们第一个缺失的非负整数。

• 这个前缀的长度为 $M$。
• 对于这个前缀中的第 $i$ 个位置 ($1 \le i \le M$)，我们放置的是数字 $i-1$。此时的前缀是 $\{0, 1, ..., i-1\}$，所以 $b_i = MEX(\{0, 1, ..., i-1\}) = i$。
• 当我们放置完 $0, 1, ..., M-1$ 后，对于之后的所有位置 ($i > M$)，无论我们放入什么数字，由于数字 $M$ 始终缺失，前缀的 $MEX$ 值将永远是 $M$。

所以，最优策略下，数组 $b$ 的形态是 $1, 2, 3, ..., M, M, ..., M$。

C++

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map>

int main() {
    // 优化输入输出速度
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    // 使用 map 统计每个数字的出现次数
    std::map<int, int> counts;
    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        counts[val]++;
    }

    std::vector<int> prefix;
    long long current_mex = 0;

    // 步骤2: 构建最优前缀 0, 1, 2, ...
    // 循环直到找不到 current_mex
    while (counts.count(current_mex) && counts[current_mex] > 0) {
        prefix.push_back(current_mex);
        counts[current_mex]--; // 使用掉一个
        current_mex++;
    }

    // 步骤3: 收集所有剩余的元素
    std::vector<int> suffix;
    for (auto const& [num, count] : counts) {
        for (int i = 0; i < count; ++i) {
            suffix.push_back(num);
        }
    }
    
    // M 的值就是 current_mex，也是 prefix 的长度
    long long M = prefix.size();
    
    // 步骤5: 计算 b 数组的最大和
    // 注意使用 long long 防止溢出
    long long max_sum = M * (M + 1) / 2 + (n - M) * M;

    std::cout << max_sum << std::endl;

    // 步骤4: 组合并输出重排后的 a 数组
    bool first = true;
    for (int val : prefix) {
        if (!first) {
            std::cout << " ";
        }
        std::cout << val;
        first = false;
    }
    for (int val : suffix) {
        if (!first) {
            std::cout << " ";
        }
        std::cout << val;
        first = false;
    }
    std::cout << std::endl;

    return 0;
}

Python

import sys
from collections import Counter

def solve():
    """
    主解决函数
    """
    # 从标准输入读取n和数组a
    n = int(sys.stdin.readline())
    a = list(map(int, sys.stdin.readline().split()))

    # 步骤1: 使用 Counter 统计频率
    counts = Counter(a)

    prefix = []
    current_mex = 0
    
    # 步骤2: 构建最优前缀 0, 1, 2, ...
    while counts[current_mex] > 0:
        prefix.append(current_mex)
        counts[current_mex] -= 1 # 使用掉一个
        current_mex += 1
    
    # 步骤3: 收集剩余元素
    suffix = []
    # 对剩余元素进行排序可以得到一个确定的输出，但非必须
    sorted_remaining_keys = sorted(counts.keys())
    for num in sorted_remaining_keys:
        suffix.extend([num] * counts[num])

    # M 的值就是 current_mex
    M = current_mex
    
    # 步骤5: 计算最大和
    max_sum = M * (M + 1) // 2 + (n - M) * M
    
    print(max_sum)
    
    # 步骤4: 组合并输出重排后的数组
    result_a = prefix + suffix
    print(*result_a)

solve()

Java

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 使用 BufferedReader 加速输入
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        
        StringTokenizer st = new StringTokenizer(reader.readLine());
        
        // 步骤1: 使用 HashMap 统计频率
        Map<Integer, Integer> counts = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int val = Integer.parseInt(st.nextToken());
            counts.put(val, counts.getOrDefault(val, 0) + 1);
        }

        List<Integer> prefix = new ArrayList<>();
        int current_mex = 0;
        
        // 步骤2: 构建最优前缀 0, 1, 2, ...
        while (counts.getOrDefault(current_mex, 0) > 0) {
            prefix.add(current_mex);
            counts.put(current_mex, counts.get(current_mex) - 1); // 使用掉一个
            current_mex++;
        }

        // 步骤3: 收集剩余元素
        List<Integer> suffix = new ArrayList<>();
        // 为了输出顺序确定，对key进行排序
        List<Integer> sortedKeys = new ArrayList<>(counts.keySet());
        Collections.sort(sortedKeys);
        
        for (int num : sortedKeys) {
            int count = counts.get(num);
            for (int i = 0; i < count; i++) {
                suffix.add(num);
            }
        }
        
        // M 的值就是 current_mex
        long M = current_mex;
        
        // 步骤5: 计算最大和，使用 long 类型
        long maxSum = M * (M + 1) / 2 + (n - M) * M;
        
        // 使用 StringBuilder 加速输出
        StringBuilder sb = new StringBuilder();
        sb.append(maxSum).append("\n");
        
        // 步骤4: 组合最终数组
        for (int i = 0; i < prefix.size(); i++) {
            sb.append(prefix.get(i)).append(" ");
        }
        for (int i = 0; i < suffix.size(); i++) {
            sb.append(suffix.get(i));
            if (i < suffix.size() - 1) {
                sb.append(" ");
            }
        }
        
        System.out.println(sb.toString());
    }
}

题目内容

小美有一个长度为 $n$ 的数组 $a$ 。你可以将 $a$ 任意重排。定义一个长度为 $n$ 的数组 $b$，其中 $b_i= MEX(a_1,a_2,...,a_i$)。你需要最大化数组 $b$ 中的元素之和。

你需要输出最大的元素和，以及一个可能的 $a$ 的重排方案。

【名词解释】

$MEX$：整数数组的 $MEX$ 定义为没有出现在数组中的最小非负整数。例如 $MEX${$1,2,3$}$=0、MEX${$0,2,5$}$=1$ 。

输入描述

第一行输入一个整数 $n(1≦n≦2·10^5)$ ，表示数组 $a$ 的长度

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(0≦a_i≦10^9)$ ，表示数组 $a$ 的元素。

输出描述

第一行输出一个整数，表示 $b$ 的元素和。

第二行输出 $n$ 个整数，表示重排后的 $a$ 。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。注意，自测运行功能可能因此返回错误结果，请自行检查等案正确性。

样例1

输入

3
1 0 1

输出

5
0 1 1

说明

将 $a$ 重排为 {$0,1,1$} 后，数组 $b$ 为 {$1,2,2$} ，元素和为 $5$ 。

可以证明不存在一个重排使得数组 $b$ 的元素和大于 $5$ 。

样例2

输入

6
0 1 2 3 4 5

输出

21
0 1 2 3 4 5