#P12289. [蓝桥杯 2024 国 Java A] 修改数位

    ID: 13945 远端评测题 3000ms 512MiB 尝试: 0 已通过: 0 难度: 3 上传者: 标签>贪心2024双指针 two-pointer蓝桥杯国赛

[蓝桥杯 2024 国 Java A] 修改数位

题目描述

给定一个 nn 位的没有前导零的十进制数 mm,你可以将其任意位 aia_i 改为任意其它数字 bib_i,花费为 biai|b_i - a_i|。我们希望通过最少的花费使得修改后的数中存在连续的 1010 位,包含了从 0099 的所有数字,且每个数字恰好出现一次。

请输出最少需要的花费是多少(修改后也要求没有前导零)。

输入格式

输入一行包含一个整数表示 mm

输出格式

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

123456789301
1

提示

样例说明

将右边第 33 位改为 22 是一种方案,此时后 1010 位恰好含有 090 \sim 9 各一个。

评测用例规模与约定

  • 对于 40%40\% 的评测用例,10n50010 \leq n \leq 500
  • 对于 60%60\% 的评测用例,10n500010 \leq n \leq 5000
  • 对于所有评测用例,10n10610 \leq n \leq 10^6,请注意 nn 表示数位个数。