当前位置：首页 > article >正文

【洛谷贪心算法题】P1094纪念品分组

article 2025/3/1 5:56:36

该题运用贪心算法，核心思想是在每次分组时，尽可能让价格较小和较大的纪念品组合在一起，以达到最少分组的目的。
在这里插入图片描述

【算法思路】

输入处理：首先读取纪念品的数量n和价格上限w，然后依次读取每件纪念品的价格，并将其存储在容器vector中
排序：使用 sort 函数对纪念品的价格进行从小到大的排序。排序的目的是方便后续使用双指针法，能快速找到价格最小和最大的纪念品。
双指针初始化：初始化两个指针 left 和 right，分别指向价格最小和最大的纪念品。同时，初始化分组数量 groups 为 0。
分组过程：
◦ 当 left 小于等于 right 时，进入循环：
◦ 如果 left 等于 right，说明只剩下一个纪念品，将分组数量加 1 并跳出循环。
◦ 如果价格最小和最大的纪念品价格之和不超过价格上限 w ，则将它们分为一组，left 指针右移一位，right 指针左移一位，分组数量加 1。
◦ 如果价格最小和最大的纪念品价格之和超过价格上限 w ，则将价格最大的纪念品单独分为一组，right 指针左移一位，分组数量加 1。
输出结果：循环结束后，输出分组的数量。

【代码示例】

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

int main() {
    int w, n;
    // 读取每组纪念品价格上限 w 和纪念品数量 n
    cin >> w;
    cin >> n;
    // 使用 n 来初始化 vector 的大小
    vector<int> P(n);
    // 读取每个纪念品的价格
    for (int i = 0; i < n; i++) {
        cin >> P[i];
    }
    // 对纪念品价格从小到大排序
    sort(P.begin(), P.end());
    // 双指针法分组
    int left = 0;
    int right = n - 1;
    // 初始化分组数量为 0
    int groupCount = 0;
    while (left <= right) {
        if (left == right) {
            // 若只剩一个纪念品，单独成一组
            groupCount += 1;
            break;
        }
        if (P[left] + P[right] <= w) {
            // 若最小和最大价格的纪念品能分在一组
            groupCount += 1;
            left += 1;
            right -= 1;
        } else {
            // 若不能，最大价格的纪念品单独成一组
            right -= 1;
            groupCount += 1;
        }
    }
    // 输出最少的分组数量
    cout << groupCount << endl;
    return 0;
}