lq1. 最大数字 · Algorithm Lab

我们有 nn 个连续的整数 1,2,3,⋯,n1,2,3,⋯,n，可以自由排列它们的顺序。然后，我们把这些数字转换成二进制表示，按照排列顺序拼接形成一个新的二进制数。我们的目标是让这个二进制数的值最大，并输出这个二进制对应的十进制表示。

输入格式

输入一行包含一个正整数 nn。

输出格式

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

样例输入

text

样例输出

text

评测用例规模与约定

对于 2020% 的评测用例，1≤n≤101≤n≤10；对于 4040% 的评测用例，1≤n≤1001≤n≤100；对于 6060% 的评测用例，1≤n≤5001≤n≤500；对于 8080% 的评测用例，1≤n≤10001≤n≤1000；对于所有评测用例，1≤n≤100001≤n≤10000。

参考解法

下面保留的是原始练习仓库中的个人作答，可在右侧工作台中独立重写，再按需揭示对照。

python


import sys
from functools import cmp_to_key

# 自定义比较函数：按二进制拼接后的大小排序
def compare(x, y):
    bx = bin(x)[2:]  # 得到x的正确二进制串（去掉0b前缀）
    by = bin(y)[2:]  # 得到y的正确二进制串
    # 比较拼接后的字典序：bx+by更大则x排在y前面（返回-1），否则y排在x前面（返回1）
    return -1 if bx + by > by + bx else 1

def main():
    n = int(sys.stdin.readline().strip())
    nums = list(range(1, n + 1))  # 生成1~n的列表
    nums.sort(key=cmp_to_key(compare))  # 按自定义规则排序
    binary_str = ''.join(bin(num)[2:] for num in nums)  # 拼接所有二进制串
    print(int(binary_str, 2))  # 二进制转十进制输出

if __name__ == "__main__":
    main()