P1094 [NOIP 2007 普及组] 纪念品分组

题目背景

NOIP2007 普及组 T2

题目描述

元旦快到了，校学生会让乐乐负责新年晚会的纪念品发放工作。为使得参加晚会的同学所获得 的纪念品价值相对均衡，他要把购来的纪念品根据价格进行分组，但每组最多只能包括两件纪念品， 并且每组纪念品的价格之和不能超过一个给定的整数。为了保证在尽量短的时间内发完所有纪念品，乐乐希望分组的数目最少。

你的任务是写一个程序，找出所有分组方案中分组数最少的一种，输出最少的分组数目。

输入格式

共 $n+2$ 行：

第一行包括一个整数 $w$，为每组纪念品价格之和的上限。

第二行为一个整数 $n$，表示购来的纪念品的总件数 $G$。

第 $3\sim n+2$ 行每行包含一个正整数 $P_i$ 表示所对应纪念品的价格。

输出格式

一个整数，即最少的分组数目。

输入输出样例 #1

输入 #1

100 
9 
90 
20 
20 
30 
50 
60 
70 
80 
90

输出 #1

6

说明/提示

$50\%$ 的数据满足：$1\le n\le 15$。

$100\%$ 的数据满足：$1\le n\le 3\times 10^4$，$80\le w\le 200$，$5\le P_i\le w$。

问题分析

1. 排序：将纪念品价格按升序排序。

2. 双指针法：

   • 左指针 i 指向最小价格，右指针 j 指向最大价格。

   • 如果 P[i] + P[j] ≤ w，则这两个纪念品可以成组，移动 i++ 和 j–。

   • 否则，只能单独将 P[j] 成组，移动 j–。

3. 计数：每次操作（无论是否配对）都增加分组数。

贪心解法（分组问题）

1. 排序：P 数组升序排序。

2. 初始化：i = 0，j = n - 1，count = 0。

3. 配对：

• 当 i ≤ j 时：

  • 如果 P[i] + P[j] ≤ w，则配对，i++，j–。

  • 否则，单独处理 P[j]，j–。

  • count++。

4. 输出：count。

代码实现

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

int main() {
    int w, n;
    cin >> w >> n;
    vector<int> P(n);
    for (int i = 0; i < n; i++) {
        cin >> P[i];
    }

    sort(P.begin(), P.end()); // 升序排序

    int i = 0, j = n - 1, count = 0;
    while (i <= j) {
        if (P[i] + P[j] <= w) {
            i++; // 可以配对
        }
        j--; // 无论如何都要处理当前最大元素
        count++;
    }

    cout << count << endl;
    return 0;
}

总结

1.排序：确保可以贪心地用最小和最大的价格尝试配对。

2.双指针：

 - i 和 j 分别指向最小和最大价格。

 - 如果 P[i] + P[j] ≤ w，则这两个可以成组。

 - 否则，P[j] 必须单独成组。

3.计数：每次循环处理至少一个纪念品，count 记录分组数。