算法设计与分析（乘船问题

目录

• 题目描述
• 解题思路
• 代码实现
• 小结：

题目描述

给定一批轮船，每艘轮船的最大载重量均为M，每艘船最多只允许装两个人，旅客总人数最多为50人。每个旅客的体重不同。现要求设计算法求出装走所有旅客所需轮船的最少数量。

输入格式：

第一行输入为每艘船的最大载重量M和旅客总人数num。
第二行输入是每个旅客的体重（整数）。

输出格式：

输出所需最少租船数量。

解题思路

本题可以使用贪心算法来解决。贪心算法的思想是在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是全局最好或最优的算法。

排序：首先将所有旅客的体重进行从小到大排序。这样可以尽可能地将最重的旅客与最轻的旅客配对，从而更有效地利用每艘船的载重能力。

双指针：使用两个指针p_l和p_r，分别指向体重数组的开始和结束。这两个指针模拟了从两端向中间配对的过程。

遍历：在p_l小于等于p_r的条件下进行循环。每次循环检查当前最轻的旅客和最重的旅客的体重之和是否小于等于船的最大载重量M。

如果是，说明这两个旅客可以装在同一艘船上，将p_l向右移动一位，p_r向左移动一位。
如果不是，说明最重的旅客无法与当前最轻的旅客配对，只能单独装一艘船（或尝试与下一个较轻的旅客配对），将p_r向左移动一位。
计数：每成功装载一对旅客（或单独装载一个旅客），就增加所需的船只数量result。

输出结果：循环结束后，输出result作为答案。

代码实现

下面是该算法的C++实现：

#include<iostream>  
#include<algorithm>  
  
using namespace std;  
  
#define MAXSIZE 50  
  
int main() {  
    // 输入数据   
    int w[MAXSIZE], num, M;  
    cin >> M >> num;  
      
    for (int i = 0; i < num; i++){  
        cin >> w[i];  
    }  
      
    // 贪心算法  
    sort(w, w + num);	// 从小到大排序   
      
    int p_l = 0;  
    int p_r = num - 1;  
    int result = 0;  
      
    while (p_l <= p_r){  
        if ((w[p_l] + w[p_r]) <= M){  
            p_l++;p_r--;  
        }  
        else{  
            p_r--;  
        }  
    }  
      
    cout << result << endl;  
    return 0;  
}