题解

题面描述

给定一个初始整数$n$和目标数$m$，要求通过若干次操作使得$n$的值不小于$m$。有两种操作：

• 操作一：将$n$更新为$2 \times n$，花费为$w_2$。
• 操作二：将$n$更新为$3 \times n$，花费为$w_3$。

问题要求在若干次操作后使得$n \ge m$，求最小花费。

思路

由于每次操作都是将$n$乘以固定的数（$2$或$3$），那么无论操作的顺序如何，最终结果都是$n \times 2^a \times 3^b$，其中$a$和$b$分别是两种操作的次数。目标是找到非负整数$a$和$b$，使得

且花费最小，花费计算为

考虑到$n$和$m$的范围很大，但由于操作每次都会快速增大$n$，所需要的$a$和$b$不会太大（例如，若只用倍增操作，$a \le 31$即可；若只用乘3操作，$b$也在几十以内），因此可以枚举$a$和$b$的所有可能组合，然后取满足条件的最小花费。

代码分析

1. 判断边界情况：若初始$n \ge m$则不需要任何操作，花费为$0$。

2. 枚举操作次数：设$a$和$b$的上限为一个足够大的数（如$32$），遍历所有可能的组合。

3. 计算结果并更新最小花费：对于每一组$(a, b)$，计算$n \times 2^a \times 3^b$，若大于等于$m$，则计算花费$cost = a \times w_2 + b \times w_3$，取所有满足条件的最小值。

4. 输出答案：枚举完成后输出最小花费。

C++

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

int main(){
    int T;
    cin >> T;
    while(T--){
        // 输入 n, m, w2，w3
        uint64_t n, m;
        int w2, w3;
        cin >> n >> m >> w2 >> w3;
        
        if(n >= m){
            cout << 0 << endl;
            continue;
        }
        
        // 初始化最小花费为一个较大值
        uint64_t ans = (uint64_t)1e18;
        
        // 枚举a和b的取值范围。由于数据范围，枚举上限取32足够
        for(int a = 0; a < 32; a++){
            // 预先计算2^a
            uint64_t pow2 = 1ULL << a; // 等同于2^a
            if(n * pow2 >= m){
                ans = min(ans, (uint64_t)a * w2);
                break;
            }
            // 枚举b
            uint64_t cur2 = n * pow2;
            uint64_t pow3 = 1;
            for(int b = 0; b < 32; b++){
                // 更新乘以3^b
                if(b > 0) pow3 *= 3;

                if(cur2 * pow3 >= m){
                    uint64_t cost = (uint64_t)a * w2 + (uint64_t)b * w3;
                    ans = min(ans, cost);
                    break; // 增加更多b只会使花费更高
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Python

# 读取测试数据组数
T = int(input())
for _ in range(T):
    # 输入 n, m, w_2, w_3
    n, m, w2, w3 = map(int, input().split())
    
    if n >= m:
        print(0)
        continue
    
    ans = float('inf')
    
    # 枚举a的取值，使用32作为上限
    for a in range(32):
        pow2 = 1 << a  # 计算2^a
        if n * pow2 >= m:
            ans = min(ans, a * w2)
            break
        cur2 = n * pow2
        pow3 = 1
        # 枚举b的取值
        for b in range(32):
            if b > 0:
                pow3 *= 3  # 计算3^b
            if cur2 * pow3 >= m:
                cost = a * w2 + b * w3
                ans = min(ans, cost)
                break  # 增加b只会增加花费
    print(ans)

Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        // 读取测试数据组数
        int T = sc.nextInt();
        for(int t = 0; t < T; t++){
            // 输入 n, m, w_2, w_3
            long n = sc.nextLong();
            long m = sc.nextLong();
            int w2 = sc.nextInt();
            int w3 = sc.nextInt();
            
      
            if(n >= m){
                System.out.println(0);
                continue;
            }
            
            long ans = Long.MAX_VALUE;
            
            // 枚举a的取值，取值上限为32
            for(int a = 0; a < 32; a++){
                long pow2 = 1L << a;  // 计算2^a
                if(n * pow2 >= m){
                    ans = Math.min(ans, (long)a * w2);
                    break;
                }
                long cur2 = n * pow2;
                long pow3 = 1;
                // 枚举b的取值，取值上限为32
                for(int b = 0; b < 32; b++){
                    if(b > 0) {
                        pow3 *= 3;  // 计算3^b
                    }
                    if(cur2 * pow3 >= m){
                        long cost = (long)a * w2 + (long)b * w3;
                        ans = Math.min(ans, cost);
                        break;  // 增加b会增加花费，故直接跳出
                    }
                }
            }
            System.out.println(ans);
        }
        sc.close();
    }
}

题目内容

开始有一个整数 $n$ ，你需要经过若干次操作，使 $n$ 的值不小于 $m$ 。

操作一：将 $n$ 更改为 $2*n$ ，花费为 $w_2$ ；

操作二：将 $n$ 更改为 $3*n$ ，花费为 $w_3$ 。

请输出需要的最小花费。

输入描述

输入第一行一个整数 $T$ ，代表接下来有 $T$ 组测试数据。

接下来 $T$ 行，每行有 $4$ 个整数 $n,m,w_2,w_3$

$1≤T≤10000$

$1≤n,m≤2^{31}-1$

$1≤w_2,w_3≤1000$

输出描述

对于每组测试数据，输出一行，一个整数代表最小花费

样例1

输入

4
1 6 2 3
4 32 3 4
2 1 1 2
1 2147483647 1 4

输出

5
8
0
31