题解：P15063 [UOI 2024 II Stage] Creating an Array

_Fust_ · 2026-01-27 13:18:59 · 题解

题解：P15063 [UOI 2024 II Stage] Creating an Array

~第一篇题解~

问题分析

核心定义与数学推导

首先明确连接操作的数学定义：对于两个数字 a 和 b，连接结果 \text{concat}(a, b) = a \times 10 + b（例如 \text{concat}(3,2) = 3 \times 10 + 2 = 32）。

题目要求最大化的总和为：

\sum_{i=1}^n \sum_{j=i}^n \text{concat}(a_i, a_j)

对总和进行拆解分析：

数组中任意两个数字 x 和 y，若 x 出现在位置 i、y 出现在位置 j 且 i \le j，则 \text{concat}(x,y) 会被计入总和；
要最大化总和，核心是确定数字的排序规则：对于任意两个数字 a 和 b，若 \text{concat}(a,b) > \text{concat}(b,a)，则 a 应排在 b 前面。

数学不等式就是：

a \times 10 + b > b \times 10 + a \implies a \text{ 排在 } b \text{ 前}

排序规则总结

自定义比较逻辑：对于数字 a 和 b，a 优先于 b 的充要条件是 a \times 10 + b > b \times 10 + a。

C++ 完整实现代码

#include <bits/stdc++.h>

using namespace std;

bool cmp(int a, int b) {
    return a * 10 + b > b * 10 + a;
}

int main() {
    vector<int> count(10);
    for (int i = 0; i < 10; ++i) {
        cin >> count[i];
    }
    vector<int> arr;
    for (int num = 0; num < 10; ++num) {
        for (int cnt = 0; cnt < count[num]; ++cnt) {
            arr.push_back(num);
        }
    }
    sort(arr.begin(), arr.end(), cmp);
    for (size_t i = 0; i < arr.size(); ++i) {
        if (i > 0) cout << " ";
        cout << arr[i];
    }
    cout << endl;
    return 0;
}

AC记录：https://www.luogu.com.cn/record/259233966