解题思路

这是一个贪心算法问题。关键点如下：

  1. 扭蛋机2号：投入 个扭蛋，可以得到 个
  2. 扭蛋机3号：投入 个扭蛋，可以得到 个
  3. 需要通过两人轮流使用扭蛋机，最终得到 个扭蛋

解题思路：

  1. 从目标数N开始反向推导
  2. 每次判断 的奇偶性：
    • 如果 是偶数，使用3号机器，因为 是整数
    • 如果 是奇数，使用2号机器，因为 是整数
  3. 每次操作后，更新 为投入的扭蛋数量
  4. 重复直到 ，记录使用的机器顺序

代码

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    string result;
    while (n > 0) {
        if (n % 2 == 0) {
            n = (n - 2) / 2;
            result += '3';
        } else {
            n = (n - 1) / 2;
            result += '2';
        }
    }
    
    reverse(result.begin(), result.end());
    cout << result << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        StringBuffer str = new StringBuffer();
        while (n > 0) {
            if (n % 2 == 0) {
                n = (n - 2) / 2;
                str.append("3");
            } else {
                n = (n - 1) / 2;
                str.append("2");
            }
        }
        
        str.reverse();
        System.out.println(str);
    }
}

n = int(input())
result = []

while n > 0:
    if n % 2 == 0:
        n = (n - 2) // 2
        result.append('3')
    else:
        n = (n - 1) // 2
        result.append('2')

print(''.join(result[::-1]))

算法及复杂度

  • 算法：贪心
  • 时间复杂度： - 每次操作将 减半
  • 空间复杂度： - 需要存储结果字符串