找游戏 - 华为OD统一考试(C卷)

OD统一考试（C卷）

分值： 200分

题解： Java / Python / C++

alt

题目描述

小扇和小船今天又玩起来了数字游戏，

小船给小扇一个正整数 n（1 ≤ n ≤ 1e9），小扇需要找到一个比 n 大的数字 m，使得 m 和 n 对应的二进制中 1 的个数要相同，如：

4对应二进制100

8对应二进制1000

其中1的个数都为1个

现在求 m 的最小值。

输入描述

输入一个正整数 n（1 ≤ n ≤ 1e9）

输出描述

输出一个正整数 m

示例1

输入：
2

输出：
4

说明：
2的二进制10，
4的二进制位100，
1的个数相同，且4是满足条件的最小数

示例2

输入：
7

输出：
11

说明：
7的二进制111，
11的二进制位1011，
1的个数相同，且11是满足条件的最小数

题解

题解分析

这道题目要求找到一个比给定的正整数 n 大的数字 m，使得它们的二进制表示中 1 的个数相同。本质上，题目要求在二进制表示中，找到一个比 n 大的具有相同数量的 1 的数。

给出的解法是使用贪心算法。首先，将 n 转换为二进制表示，然后通过贪心地找到可以将某个 0 变成 1 的位置，使得数字变大，同时保持 1 的个数不变。最后输出这个结果。

解题思路

将给定的十进制数 n 转换为二进制表示，并在末尾添加一个 0。
使用贪心算法找到可以将某个 0 变成 1 的位置的索引 idx。
调整 idx 位 0 变成 1，同时调整 idx 前的位，使得低位为 1，高位为 0，且二进制中 1 的个数不变。
输出调整后的结果。

Java

import java.util.Scanner;
import java.util.ArrayList;
/**
 * @author code5bug
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        System.out.println(solve(n));
    }

    // 解决问题的函数
    public static int solve(int n) {
        ArrayList<Integer> bs = new ArrayList<>();
        // 转换为二进制
        while (n > 0) {
            bs.add(n % 2);
            n /= 2;
        }
        // 在列表末尾添加一个 0，以便处理
        bs.add(0);

        // 贪心的寻找可以将 0 变成 1 的地方的索引 idx（使得数字变大）
        // idx 满足低位存在 1 且 bs.get(idx) == 0
        int idx = 0, oneCnt = 0;
        for (; idx < bs.size(); idx++) {
            if (oneCnt > 0 && bs.get(idx) == 0) {
                break;
            }
            oneCnt += bs.get(idx);
        }

        // 将 idx 位 0 变成 1，同时 idx 前的位也相应调整
        // 调整规则：低位 1，高位 0，且二进制中 1 的个数不变
        for (int i = 0; i < idx; i++) {
            bs.set(i, (i < oneCnt - 1) ? 1 : 0);
        }

        // idx 位 0 变成 1，后面的位全部保持不变
        bs.set(idx, 1);

        // 计算最终结果
        int result = 0, base = 1;
        for (int i = 0; i < bs.size(); i++) {
            result += bs.get(i) * base;
            base *= 2;
        }

        return result;
    }
}

Python

def solve(n):
    bs = []
    # 转换为二进制
    while n > 0:
        bs.append(n % 2)
        n //= 2
    # 在列表末尾添加一个 0，以便处理
    bs.append(0)

    # 贪心的寻找可以将 0 变成 1 的地方的索引 idx（使得数字变大）
    # idx 满足低位存在 1 且 bs[idx] == 0
    idx, one_cnt = 0, 0
    while idx < len(bs):
        if one_cnt > 0 and bs[idx] == 0:
            break
        one_cnt += bs[idx]
        idx += 1

    # 将 idx 位 0 变成 1，同时 idx 前的位也相应调整
    # 调整规则：低位 1，高位 0，且二进制中 1 的个数不变
    for i in range(idx):
        bs[i] = 1 if i < one_cnt - 1 else 0

    # idx 位 0 变成 1，后面的位全部保持不变
    bs[idx] = 1

    # 计算最终结果
    result, base = 0, 1
    for bit in bs:
        result += bit * base
        base *= 2

    return result


if __name__ == "__main__":
    n = int(input())
    print(solve(n))

C++

#include <iostream>
#include <vector>

using namespace std;

int solve(int n) {
    vector<int> bs;
    // 转换为二进制
    while (n > 0) {
        bs.push_back(n % 2);
        n /= 2;
    }
    // 在数组末尾添加一个 0，以便处理
    bs.push_back(0);

    // 贪心的寻找可以 0 变成 1 的地方 idx (使得数字变大)
    // idx 满足低位存在 1 且 bs[idx] == 0
    int idx = 0, oneCnt = 0;
    for (; idx < bs.size(); idx++) {
        if (oneCnt > 0 && bs[idx] == 0) break;
        oneCnt += bs[idx];
    }

    // 将 idx 位 0 变成 1，同时 idx 前的位也相应调整
    // 调整规则： 低位 1 ，高位 0， 且 二进制中 1 的个数不变
    for (int i = 0; i < idx; i++) {
        bs[i] = (i < oneCnt - 1) ? 1 : 0;
    }

    // idx 位 0 变成 1 ，后面的位全部保持不变
    bs[idx] = 1;

    int result = 0, base = 1;
    for (int bit : bs) {
        result += bit * base;
        base *= 2;
    }

    return result;
}

int main() {
    int n;
    cin >> n;
    cout << solve(n) << endl;

    return 0;
}