徐老师的装饰任务
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
蔚蓝之境是一个神秘的水上王国,由 2021 座小岛组成,编号从 1 到 2021。每两座岛之间都有一座桥梁直接相连,形成一张密集的桥梁网络。
为了庆祝一年一度的传统节日,徐老师被邀请作为总设计师为这些桥梁进行节日装饰。每座桥梁的装饰费用由两个相连岛屿编号的数字差异决定,具体计算方式如下:
- 对于两个岛屿编号 (a) 和 (b),先拆分成十进制的每一位数字;
- 比较对应位的数字,若数字不同,则将这两位数字的和加入费用中;
- 不存在的高位视作 0,不参与计算。
例如:编号 2021 和 922,拆分为 (2,0,2,1) 与 (0,9,2,2),比较对应位差异:
- 千位:2 vs 0,不同,费用加 2 + 0 = 2
- 百位:0 vs 9,不同,费用加 0 + 9 = 9
- 十位:2 vs 2,相同,不加
- 个位:1 vs 2,不同,费用加 1 + 2 = 3
总费用为 (2 + 9 + 3 = 14)。
徐老师需要选择一批桥梁进行装饰,要求装饰后的桥梁能够保证从任意一座岛屿都能通过已装饰的桥梁到达其他任意岛屿(即桥梁构成连通图),且装饰总费用最低。
请你帮徐老师计算至少需要花费多少费用,才能完成这项任务。
输入格式
本题无输入。
输出格式
输出一个整数,表示最低总装饰费用。
数据范围
- 岛屿数量固定为 2021。
- 任何计算均保证在 32 位整数范围内。
示例说明
此题无示例输入输出,需直接输出计算结果。