笔试时间：2025年8月13日

往年笔试合集：

2023春招秋招笔试合集

2024春招秋招笔试合集

第一题：超级重排

Tk 有一个长度为 n 的数组{a1,a2,...,an}。Tk 定义这个数组的权值为：。为了使数组的权值最大，Tk 提出如下超级重排流程：·将所有元素的十进制表示按原序拼接成一个字符串；·对该字符串中的所有字符进行重新排列；·按照原元素的位数切分字符串，恢复为 n 个新数字。或者换句话说，首先，收集所有数字的每一个单独的数位；其次，对于每一个原始数字 ai，记录下它的位数。你必须用收集到的所有数位来构造 n 个新的数字，其中第 j 个新数字的位数必须与原始数组中第 j 个数字 aj 的位数相同。你的目标是找到一种分配这些数位的方式，使得这 n 个新数字的总和达到最大。

输入描述

第一行输入一个整数 n(1≤n≤2*105)，表示数组长度。

第二行输入 n 个整数a1,a2,...,an（1≤ai≤109）表示数组 a，题目保证每个元素的十进制表示中不含字符 '0'

输出描述

输出一个整数，表示经过超级重排后数组的最大权值。

样例输入

2

36 15

样例输出

114

参考题解

每个位置的权重是 10^e，其中 e 是它到右端的距离（个位 e=0，十位 e=1，百位 e=2…）。所有数字的位数是固定的，所以每个原数字的高位权重大，低位权重小。最优策略：把所有位置（带权重的格子）统一考虑，按权重从大到小分配最大的数字（重排不等式）。记录位数统计每个 ai 的位数 Li。统计所有数字字符例如 [36,15] [36, 15] [36,15] → [3, 6, 1, 5]。统计每个位置的权重如果一个数字的长度是 L，它的位权分别是：10^{L-1}, 10^{L-2}, ....., 10^0把所有数字的位权放到一个“权重桶”里。排序匹配将权重从大到小排序。将数字字符从大到小排序。一一对应，最大数字放到最大权重位置。计算总和不需要真正构造新数字，只要累加：贡献=数字×位权。

C++：

#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
using boost::multiprecision::cpp_int;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    if (n <= 0) { cout << 0 << "\n"; return 0; }

    vector<string> tokens;
    tokens.reserve(n);
    for (int i = 0; i < n; ++i) {
        string tok; cin >> tok;
        tokens.push_back(tok);
    }

    int maxL = 0;
    vector<long long> digit_cnt(10, 0);
    vector<int> lens; lens.reserve(n);
    for (auto &tok : tokens) {
        int L = (int)tok.size();
        lens.push_back(L);
        maxL = max(maxL, L);
        for (char ch : tok) {
            int d = ch - '0';
            ++digit_cnt[d];
        }
    }

    // len_cnt[L] = count of tokens with length == L
    vector<long long> len_cnt(maxL + 1, 0);
    for (int L : lens) ++len_cnt[L];

    // suff_ge[L] = number of tokens with length >= L
    vector<long long> suff_ge(maxL + 2, 0);
    long long s = 0;
    for (int L = maxL; L >= 1; --L) {
        s += len_cnt[L];
        suff_ge[L] = s;
    }

    // pow10[e] = 10^e (big integer)
    vector<cpp_int> pow10(maxL > 0 ? maxL : 1);
    pow10[0] = 1;
    for (int e = 1; e < maxL; ++e) pow10[e] = pow10[e - 1] * 10;

    cpp_int ans = 0;
    int d = 9;
    for (int e = maxL - 1; e >= 0; --e) {
        long long slots = suff_ge[e + 1];
        while (slots > 0) {
            while (d >= 0 && digit_cnt[d] == 0) --d;
            if (d < 0) break;
            long long take = (long long)min<long long>(digit_cnt[d], slots);
            // ans += take * d * 10^e
            cpp_int contrib = pow10[e] * (long long)d * take;
            ans += contrib;
            digit_cnt[d] -= take;
            slots -= take;
        }
    }

    cout << ans << "\n";
    return 0;
}

Java：

import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        line = br.readLine();
        if (line == null || line.trim().isEmpty()) {
            System.out.println(0);
            return;
        }
        int n = Integer.parseInt(line.trim());
        if (n <= 0) {
            System.out.println(0);
            return;
        }

        StringTokenizer st = new StringTokenizer("");
        String[] tokens = new String[n];
        int got = 0;
        while (got < n) {
            if (!st.hasMoreTokens()) {
                String l = br.readLine();
                if (l == null) break;
                st = new StringTokenizer(l);
                continue;
            }
            tokens[got++] = st.nextToken();
        }
        if (got < n) { // 输入不足时按 0 处理
            System.out.println(0);
            return;
        }

        int maxL = 0;
        long[] digitCnt = new long[10];
        int[] lens = new int[n];
        for (int i = 0; i < n; i++) {
            String tok = tokens[i];
            int L = tok.length();
            lens[i] = L;
            if (L > maxL) maxL = L;
            for (int k = 0; k < L; k++) {
                int d = tok.charAt(k) - '0';
                digitCnt[d]++;
            }
        }

        long[] lenCnt = new long[maxL + 1];
        for (int L : lens) lenCnt[L]++;

        long[] suffGe = new long[maxL + 2];
        long s = 0;
        for (int L = maxL; L >= 1; L--) {
            s += lenCnt[L];
            suffGe[L] = s;
        }

        BigInteger[] pow10 = new BigInteger[Math.max(1, maxL)];
        pow10[0] = BigInteger.ONE;
        for (int e = 1; e < maxL; e++) {
            pow10[e] = pow10[e - 1].multiply(BigInteger.TEN);
        }

        BigInteger ans = BigInteger.ZERO;
        int d = 9;
        for (int e = maxL - 1; e >= 0; e--) {
            long slots = suffGe[e + 1];
            while (slots > 0) {
                while (d >= 0 && digitCnt[d] == 0) d--;
                if (d < 0) break;
                long take = Math.min(digitCnt[d], slots);
                BigInteger contrib = pow10[e]
                        .multiply(BigInteger.valueOf(d))
                        .multiply(BigInteger.valueOf(take));
                ans = ans.add(contrib);
                digitCnt[d] -= take;
                slots -= take;
            }
        }

        System.out.println(ans.toString());
    }
}

Python：

def main():
    n = int(input())
    tokens = input().split()
    maxL = 0
    len_cnt = [0] * 11
    digit_cnt = [0] * 10
    for tok in tokens:
        L = len(tok)
        len_cnt[L] += 1
        if L > maxL:
            maxL = L
        for ch in tok:
            d = int(ch)
            digit_cnt[d] += 1
    suff_ge = [0] * (maxL + 2)
    s = 0
    for L in range(maxL, 0, -1):
        s += len_cnt[L]
        suff_ge[L] = s
    pow10 = [1]