题解 | 星际穿越

解题思路

这是一个二分查找问题。需要找到最大的 $x$ ，使得 $x + x² ≤ h$ 。

关键点：

使用二分查找找到最大可能的 $x$
注意数据范围，需要使用long long类型
防止溢出，需要仔细处理乘法运算
边界条件的处理

算法步骤：

对可能的损耗值进行二分查找
检查当前损耗值是否满足条件
更新搜索范围

代码

cpp
java
python

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

class Solution {
public:
    long long solve(long long h) {
        long long left = 0, right = min((long long)1e9, h);
        long long result = 0;
        
        while (left <= right) {
            long long mid = left + (right - left) / 2;
            
            // 检查是否满足条件：x + x² ≤ h
            if (mid <= h / (mid + 1)) {
                result = mid;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
};

int main() {
    long long h;
    cin >> h;
    
    Solution solution;
    cout << solution.solve(h) << endl;
    
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        public long solve(long h) {
            long left = 0, right = Math.min((long)1e9, h);
            long result = 0;
            
            while (left <= right) {
                long mid = left + (right - left) / 2;
                
                // 检查是否满足条件：x + x² ≤ h
                // 避免溢出，转换为 x ≤ h/(x+1)
                if (mid <= h / (mid + 1)) {
                    result = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            
            return result;
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long h = sc.nextLong();
        
        Solution solution = new Solution();
        System.out.println(solution.solve(h));
        
        sc.close();
    }
}

class Solution:
    def solve(self, h: int) -> int:
        left, right = 0, min(int(1e9), h)
        result = 0
        
        while left <= right:
            mid = (left + right) // 2
            
            # 检查是否满足条件：x + x² ≤ h
            # 避免溢出，转换为 x ≤ h/(x+1)
            if mid <= h // (mid + 1):
                result = mid
                left = mid + 1
            else:
                right = mid - 1
        
        return result

# 读取输入
h = int(input())

solution = Solution()
print(solution.solve(h))

题解 | 星际穿越

解题思路

关键点：

算法步骤：

代码

算法及复杂度

时间复杂度

空间复杂度