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

kmszcll2024 · 2026-01-26 17:17:22 · 题解

此题不难。

题意

给定数字 0 到 9 的各自个数，需要构造一个数，使得数组中所有非降序位置对 (i,j)（即 i \le j）的连接值之和最大。连接值 \operatorname{concat}(a_i, a_j) 表示将 a_i 和 a_j 按顺序拼接形成的数）。由于本题中每个元素均为一位数字，因此连接值等于 10 \times a_i + a_j。

解题思路

我们首先分析目标函数。设数组长度为 n，数组元素为 a_1, a_2, \dots, a_n（每个 a_i 是 0 到 9 的数字）。需要最大化的和为：

S = \sum_{i=1}^n \sum_{j=i}^n (10 \cdot a_i + a_j)

对于固定的位置 i，数字 a_i 在求和中的贡献可以分为两部分：

作为第一个数字：出现在所有 j \ge i 的配对中，贡献 10 \cdot a_i，共 (n-i+1) 次，总贡献为 10 \cdot a_i \cdot (n-i+1)。
作为第二个数字：出现在所有 k \le i 的配对中（即配对 (k,i)），贡献 a_i，共 i 次，总贡献为 a_i \cdot i。

因此，a_i 对总和的贡献为：

a_i \cdot \big[10 \cdot (n-i+1) + i\big]

将系数化简：

10 \cdot (n-i+1) + i = 10n - 10i + 10 + i = 10n + 10 - 9i

由于 10n+10 是常数，系数随 i 增大而递减。即位置越靠前（i 越小），系数越大。

我们需要安排给定的数字到各个位置，使得总和 S = \sum_{i=1}^n c_i \cdot a_i 最大，其中 c_i = 10n+10-9i 是递减序列。

所以从大到小排。输出即可。

做出来了。

代码

#include<bits/stdc++.h>
using namespace std;
int cnt[15];
int main(){
    for(int i=0;i<=9;i++){
        scanf("%d",&cnt[i]);
    }
    for(int i=9;i>=0;i--){
        while(cnt[i]){cnt[i]--;printf("%d ",i);}
    }
    return 0;
}