#P13312. [2025年队测]最小和

    ID: 12496 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 9 上传者: 标签>CF2600提高+/省选-数位 DP基数排序增量维护滚动数组

[2025年队测]最小和

题目描述

对正整数 xx,用 f(x)f(x) 表示 xx 的十进制各位数字之和。

给定一个由正整数组成的序列 A=(A1,…,AN)A=(A_1,\ldots,A_N)。请选择一个非负整数 xx,求 ∑i=1Nf(Ai+x)\displaystyle\sum_{i=1}^N f(A_i+x) 的最小值。

输入格式

第一行一个整数 NN。

第二行 NN 个整数 A1,A2,…,ANA_1,A_2,\ldots,A_N。

输出格式

输出一行一个整数,表示答案。

样例

4
4 13 8 6
14

取 x=7x=7,则 f(11)+f(20)+f(15)+f(13)=14f(11)+f(20)+f(15)+f(13)=14。

4
123 45 678 90
34

取 x=22x=22,则 f(145)+f(67)+f(700)+f(112)=34f(145)+f(67)+f(700)+f(112)=34。

原题另列样例 3 至 5,对应子任务 1、4、6。

数据规模与约定

对于全部数据,1≤N≤1061\le N\le10^6,1≤Ai<1091\le A_i<10^9。

原赛子任务 特殊性质 原赛分值
1 N,Ai≤2000N,A_i\le2000 10
2 N≤2000N\le2000
3 Ai≤2000A_i\le2000 15
4 每个 AiA_i 的十进制各位数字均不超过 88
5 N≤2×105N\le2\times10^5 25
6 无特殊限制

原题 PDF