题解 | #平均值#

题目链接

平均值

题目描述

给出两个正整数 x 和 y，每次可以选择其中一个数字，然后将其替换为 x 和 y 的几何平均数或者平方平均数。问最少经过几次替换，可以使得两个数相等。

注：

几何平均数： $\lceil \sqrt{x \cdot y} \rceil$ （向上取整）
平方平均数： $\lfloor \sqrt{\frac{x^2 + y^2}{2}} \rfloor$ （向下取整）

输入:

一行两个正整数 x 和 y

输出:

输出一个非负整数，表示最少的替换次数

解题思路

这是一个搜索问题，可以通过以下步骤解决：

关键发现：
- 每次可以选择两种平均数中的一种
- 可以选择替换任意一个数
- 需要找到最少的替换次数
解题策略：
- 使用BFS搜索所有可能的状态
- 记录已访问的状态避免重复
- 当两数相等时返回步数
具体步骤：
- 使用队列存储状态和步数
- 对每个状态尝试所有可能的操作
- 记录已访问状态避免循环
- 找到最短路径

代码

c++
java
python

#include <bits/stdc++.h>
using namespace std;

struct State {
    int x, y, steps;
    State(int _x, int _y, int _s): x(_x), y(_y), steps(_s) {}
};

int main() {
    int x, y;
    cin >> x >> y;
    
    if(x == y) {
        cout << 0 << endl;
        return 0;
    }
    
    queue<State> q;
    set<pair<int,int>> visited;
    
    q.push(State(x, y, 0));
    visited.insert({x, y});
    
    while(!q.empty()) {
        State curr = q.front();
        q.pop();
        
        // 计算两种平均数
        int geo = ceil(sqrt(1.0 * curr.x * curr.y));
        int sqr = floor(sqrt((1.0 * curr.x * curr.x + curr.y * curr.y) / 2));
        
        // 尝试替换x
        if(!visited.count({geo, curr.y})) {
            if(geo == curr.y) return cout << curr.steps + 1 << endl, 0;
            q.push(State(geo, curr.y, curr.steps + 1));
            visited.insert({geo, curr.y});
        }
        if(!visited.count({sqr, curr.y})) {
            if(sqr == curr.y) return cout << curr.steps + 1 << endl, 0;
            q.push(State(sqr, curr.y, curr.steps + 1));
            visited.insert({sqr, curr.y});
        }
        
        // 尝试替换y
        if(!visited.count({curr.x, geo})) {
            if(geo == curr.x) return cout << curr.steps + 1 << endl, 0;
            q.push(State(curr.x, geo, curr.steps + 1));
            visited.insert({curr.x, geo});
        }
        if(!visited.count({curr.x, sqr})) {
            if(sqr == curr.x) return cout << curr.steps + 1 << endl, 0;
            q.push(State(curr.x, sqr, curr.steps + 1));
            visited.insert({curr.x, sqr});
        }
    }
    
    return 0;
}

import java.util.*;

public class Main {
    static class State {
        int x, y, steps;
        State(int x, int y, int steps) {
            this.x = x;
            this.y = y;
            this.steps = steps;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        
        if(x == y) {
            System.out.println(0);
            return;
        }
        
        Queue<State> q = new LinkedList<>();
        Set<String> visited = new HashSet<>();
        
        q.offer(new State(x, y, 0));
        visited.add(x + "," + y);
        
        while(!q.isEmpty()) {
            State curr = q.poll();
            
            // 计算两种平均数
            int geo = (int)Math.ceil(Math.sqrt(1.0 * curr.x * curr.y));
            int sqr = (int)Math.floor(Math.sqrt((1.0 * curr.x * curr.x + curr.y * curr.y) / 2));
            
            // 尝试替换x
            String key = geo + "," + curr.y;
            if(!visited.contains(key)) {
                if(geo == curr.y) {
                    System.out.println(curr.steps + 1);
                    return;
                }
                q.offer(new State(geo, curr.y, curr.steps + 1));
                visited.add(key);
            }
            key = sqr + "," + curr.y;
            if(!visited.contains(key)) {
                if(sqr == curr.y) {
                    System.out.println(curr.steps + 1);
                    return;
                }
                q.offer(new State(sqr, curr.y, curr.steps + 1));
                visited.add(key);
            }
            
            // 尝试替换y
            key = curr.x + "," + geo;
            if(!visited.contains(key)) {
                if(geo == curr.x) {
                    System.out.println(curr.steps + 1);
                    return;
                }
                q.offer(new State(curr.x, geo, curr.steps + 1));
                visited.add(key);
            }
            key = curr.x + "," + sqr;
            if(!visited.contains(key)) {
                if(sqr == curr.x) {
                    System.out.println(curr.steps + 1);
                    return;
                }
                q.offer(new State(curr.x, sqr, curr.steps + 1));
                visited.add(key);
            }
        }
    }
}

from collections import deque
import math

def solve(x, y):
    if x == y:
        return 0
    
    q = deque([(x, y, 0)])  # (x, y, steps)
    visited = {(x, y)}
    
    while q:
        curr_x, curr_y, steps = q.popleft()
        
        # 计算两种平均数
        geo = math.ceil(math.sqrt(curr_x * curr_y))
        sqr = math.floor(math.sqrt((curr_x * curr_x + curr_y * curr_y) / 2))
        
        # 尝试替换x
        if (geo, curr_y) not in visited:
            if geo == curr_y:
                return steps + 1
            q.append((geo, curr_y, steps + 1))
            visited.add((geo, curr_y))
        if (sqr, curr_y) not in visited:
            if sqr == curr_y:
                return steps + 1
            q.append((sqr, curr_y, steps + 1))
            visited.add((sqr, curr_y))
        
        # 尝试替换y
        if (curr_x, geo) not in visited:
            if geo == curr_x:
                return steps + 1
            q.append((curr_x, geo, steps + 1))
            visited.add((curr_x, geo))
        if (curr_x, sqr) not in visited:
            if sqr == curr_x:
                return steps + 1
            q.append((curr_x, sqr, steps + 1))
            visited.add((curr_x, sqr))

x, y = map(int, input().split())
print(solve(x, y))

算法及复杂度

算法：BFS（广度优先搜索）
时间复杂度： $\mathcal{O}(n)$ - n 是可能的状态数，与输入数值大小相关
空间复杂度： $\mathcal{O}(n)$ - 需要存储已访问的状态

注意：

需要使用浮点数计算平均数，避免整数除法的误差
注意向上取整和向下取整的处理
使用visited集合避免重复访问相同状态
当找到相等的数时立即返回结果