洛谷P1007士兵过桥问题详解 C++贪心算法实现与优化

题目解读

这道题目描述了一座长度为L的桥上有n个士兵，每个士兵每秒可以向左或向右移动1个单位。当士兵到达桥的端点(0或L+1)时离开桥。要求计算所有士兵离开桥的最小时和最大时间。

解题思路

1. 最小时计算：每个士兵选择离自己最近的桥端离开，取所有士兵中最大的时间

2. 最大时计算：考虑最极端情况，所有士兵都向同一个方向移动

3. 使用贪心算法思想，无需考虑具体移动顺序

解题步骤

1. 输入桥长L和士兵数n

2. 处理n=0的特殊情况

3. 读取并存储所有士兵位置

4. 对士兵位置进行排序

5. 计算最小时

6. 计算最大时

7. 输出结果

代码实现

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

int arr[5002][2]={0}; // 备用数组，本题未使用int soldier[5002]={0}; // 存储士兵位置的数组int main(){
    int L,n; // L:桥的长度，n:士兵数量
    cin >>L; // 输入桥的长度
    cin>>n; // 输入士兵数量
    
    // 处理没有士兵的特殊情况
    if(n==0){
        cout<<"0 0";
        return 0;
    }    
    // 读取每个士兵的位置
    for(int i=0;i<n;i++){
        int tmp;
        cin>>tmp;
        soldier[i]=tmp;
    }    
    // 对士兵位置进行排序
    sort(soldier,soldier+n);
    
    int out1=-1,out2=-1; // out1:最小时间，out2:最大时间
    
    // 计算所有士兵离开桥的最小时间中的最大值
    for(int i=0;i<n;i++){
        int now=soldier[i];        // 每个士兵可以选择向左或向右走，取较小值
        // 然后取所有士兵中的最大值
        out1=max(min(now,L+1-now),out1);
    }    
    // 计算所有士兵离开桥的最大时间
    // 即最左边的士兵向右走或最右边的士兵向左走的时间
    out2=max(L+1-soldier[0],soldier[n-1]);    
    // 输出结果
    cout<<out1<<" "<<out2;

    return 0;
}

总结

本题通过贪心算法巧妙解决了士兵过桥问题，关键在于理解最小时和最大时的计算原理，掌握排序预处理技巧，学会分析极端情况。该算法时间复杂度为O(nlogn)，主要来自排序步骤，是效率较高的解法。