1 条题解
-
0
题目分析
考点:贪心、分类讨论。
要求构造出满足「每一位数字出现次数固定」「相邻两位不同」「无前导零」的最小正整数。
爆搜部分分:直接搜索全排列即可。
特殊性质(只有两个数字非零):设这两个数字为 和 。此时最终的美丽数只可能是 或 两种形式之一,分类讨论一下即可。
特殊性质(三个数字非零):设这三个数字为 。贪心策略是从数位高位到低位依次放置:优先放当前最小的数字,如果与上一位相同则放下一个。但需要判断「剩下的数字还能不能构成美丽数」。
能构成的充要条件是:设剩余数字中出现次数最多的那个数字出现 次、其余数字总数为 ,则必须满足 。只有这样才能保证相同数字不相邻。
关于不能有前导零:可以假设前一位放置的是数字 ,这样处理自然就排除了前导零。
正解:沿用上面的思路,从高位到低位依次尝试放置 ,判断「放在这一位之后,剩余数字还能否构成美丽数」——同样使用上面那条 的充要条件。由于数字种类只有 10 种,暴力判断的复杂度很小。
若所有数字都无法放置(即任何情况下都无法避免相邻重复),则输出 。
- 1
信息
- ID
- 112
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者