题解 | #数轴#

解题思路

这是一个数轴上的移动问题：

1. 个朋友在数轴上的不同位置
2. 每个朋友可以向左或向右移动 距离
3. 要求移动后最左边和最右边朋友的距离最小

解题步骤：

1. 先将所有点排序
2. 枚举分界点 ，前 个点向右移动，后面的点向左移动
3. 对每种分界情况，计算最大值和最小值的差
4. 取所有情况中的最小值

代码

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

const int MAXN = 55;

int main() {
    int n, s;
    int x[MAXN];
    
    // 读入数据
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        cin >> x[i];
    }
    
    // 排序
    sort(x + 1, x + n + 1);
    
    // 初始范围
    int range = x[n] - x[1];
    
    // 枚举分界点
    for (int i = 1; i < n; i++) {
        int minVal = INT_MAX;
        int maxVal = INT_MIN;
        
        // 处理前i个点（向右移动）
        for (int j = 1; j <= i; j++) {
            minVal = min(minVal, x[j] + s);
            maxVal = max(maxVal, x[j] + s);
        }
        
        // 处理后面的点（向左移动）
        for (int k = i + 1; k <= n; k++) {
            maxVal = max(maxVal, x[k] - s);
            minVal = min(minVal, x[k] - s);
        }
        
        // 更新最小范围
        range = min(range, maxVal - minVal);
    }
    
    cout << range << endl;
    return 0;
}

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static final int MAXN = 55;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int s = sc.nextInt();
        int[] x = new int[MAXN];
        
        // 读入数据
        for (int i = 1; i <= n; i++) {
            x[i] = sc.nextInt();
        }
        
        // 排序
        Arrays.sort(x, 1, n + 1);
        
        // 初始范围
        int range = x[n] - x[1];
        
        // 枚举分界点
        for (int i = 1; i < n; i++) {
            int minVal = Integer.MAX_VALUE;
            int maxVal = Integer.MIN_VALUE;
            
            // 处理前i个点（向右移动）
            for (int j = 1; j <= i; j++) {
                minVal = Math.min(minVal, x[j] + s);
                maxVal = Math.max(maxVal, x[j] + s);
            }
            
            // 处理后面的点（向左移动）
            for (int k = i + 1; k <= n; k++) {
                maxVal = Math.max(maxVal, x[k] - s);
                minVal = Math.min(minVal, x[k] - s);
            }
            
            // 更新最小范围
            range = Math.min(range, maxVal - minVal);
        }
        
        System.out.println(range);
        sc.close();
    }
}

# 读入数据
n, s = map(int, input().split())
x = [-10**9] + list(map(int, input().split()))  # 1-based indexing

# 排序
x.sort()

# 初始范围
range_val = x[n] - x[1]

# 枚举分界点
for i in range(1, n):
    min_val = float('inf')
    max_val = float('-inf')
    
    # 处理前i个点（向右移动）
    for j in range(1, i + 1):
        min_val = min(min_val, x[j] + s)
        max_val = max(max_val, x[j] + s)
    
    # 处理后面的点（向左移动）
    for k in range(i + 1, n + 1):
        max_val = max(max_val, x[k] - s)
        min_val = min(min_val, x[k] - s)
    
    # 更新最小范围
    range_val = min(range_val, max_val - min_val)

print(range_val)

算法及复杂度

• 算法：排序 + 枚举
• 时间复杂度：，其中 是朋友的数量
• 空间复杂度：，用于存储位置数组