解题思路

算法概述

转成字符串处理
将输入的正整数 $n$ 转为长度为 $L$ 的字符串 s。
贪心+回溯构造
从最高位到最低位逐位决定数字。对第 i 位，我们在合法范围内（若受上界约束则不超过 s[i]，否则不超过 9；且不小于前一位已定的数字）的候选数字中，从大到小尝试最优选择。
可行性剪枝
每选一个数字 d 之后，根据当前已选的数字和剩余位置，可算出可能的最小/最大剩余位数和：

P3716.第3题-虚拟货币挖矿算力匹配

1000ms

Tried: 357

Accepted: 64

Difficulty: 7

所属公司 : 华为

算法与标签>贪心算法

题目内容

在一个虚拟货币挖矿系统中，每个矿工拥有一定的算力值 $n$ (范围在 $1$ 到 $10^{18}$ 之间)。系统需要为每个矿工分配一个算力档位，这个档位必须是小于等于矿工当前算力 $n$ 的最大“稳定算力档”，并且这个档位的算力值各个数位之和必须是一个质数(质数又称素数。一个大于 $1$ 的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数)。“稳定算力档”定义为从左到右每一位数字都不小于前一位数字，例如 $123、111、399$ 都是符合要求的稳定算力档，像 $121、897$

这种则不符合要求。合理分配算力档位有助于提高挖矿效率和稳定性。

输入描述

给定一个正整数 $n(1≤n≤10^{18})$

输出描述

返回小于等于 $n$ 的最大稳定算力档，且该整数的所有数位之和为质数。如果不存在这样的整数，则返回 $-1$

样例1

输入

输出

说明

$111$ 本身即是"稳定算力档"，从左到右每一位数字都不小于前一位数字， $1+1+1=3$ 是质数，所以函数返回 $111$

样例2

输入

输出

-1

说明

小于等于 $1$ 的"稳定算力档"只有 $1$ , $1$ 的数位之和为 $1$ , $1$ 不是质数(质数定义为大于 $1$ 的自然数中，除了 $1$ 和它自身外，不能被其他自然数整除的数)，所以函数返回 $-1$

样例3

输入

输出

说明

首先小于等于 $123$ 的“稳定算力档"有 $123、122、111$ 等。 $123$ 的数位之和为 $1+2+3=6$ ,不是质数，不符合条件。再继续找是 $122$ ，数位之和为 $1+2+2=5$ 是质数符合"稳定算力档条件。 $111$ 的数位之和 $1+1+1=3$ 也为质数也满足"稳定算力档"的条件，但 $111$ 小于 $122$ ，所以小于等于 $n$ 的最大稳定算力档为 $122$ ，函数返回 $122$ 。

输入

预期输出（选填）

解题思路

算法概述

P3716.第3题-虚拟货币挖矿算力匹配

题目内容

输入描述

输出描述

样例1

说明

样例2

说明

样例3

说明

Status

Development

Support

About