[NOIP2007-普及] 纪念品分组

题目描述

给定每组价格之和的上界 $w$ 与 $n$ 件纪念品的价格 $P_i$ （ $5 \le P_i \le w$ ），要把纪念品分组，每组最多 2 件且价格之和不超过 $w$ ，求最少分组数。

输入：第 1 行 $w$ ，第 2 行 $n$ ，接下来 $n$ 行每行一个 $P_i$ 。输出：最少分组数。

样例： $w=100, n=9$ ，价格 $90,20,20,30,50,60,70,80,90$ ，输出 $6$ 。数据范围 $1 \le n \le 30000$ 。

思路

排序后，设最便宜的未处理件为 $P_{\min}$ ，最贵的为 $P_{\max}$ 。若 $P_{\min}+P_{\max}>w$ ，则 $P_{\max}$ 只能单独成组；否则把两者配成一组不会使最优解变差（交换论证）。于是用双指针从两端向中间扫描，能凑就凑，凑不上就让贵的单独成组。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 07:12
# update_at: 2026-10-02 07:12

import sys


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    limit = next(data)  # 每组价格之和的上界 w
    n = next(data)      # 纪念品件数
    prices = sorted(next(data) for _ in range(n))

    # 双指针贪心：最贵的必须和某个最便宜的搭（或独自成组），
    # 因为它和任何更贵的搭都会浪费配额，只可能让组数变多。
    groups = 0
    lo, hi = 0, n - 1
    while lo <= hi:
        if lo < hi and prices[lo] + prices[hi] <= limit:  # 最便宜的能陪最贵的
            lo += 1
        hi -= 1
        groups += 1  # prices[hi] 处理完毕：要么成组，要么落单

    print(groups)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 13:42
 * update_at: 2026-10-06 13:42
 */

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

typedef long long ll;

const int MAXN = 30005;

ll w;           // 每组价格之和的上界
int n;          // 纪念品件数
ll p[MAXN];     // 各纪念品价格

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> w;
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> p[i];

    sort(p, p + n); // 升序排序

    int lo = 0, hi = n - 1;
    int groups = 0;
    while (lo <= hi) {
        if (lo < hi && p[lo] + p[hi] <= w) // 最便宜的能陪最贵的
            ++lo;                           // 配对成功，lo 前进
        --hi;                               // hi 每轮都处理掉
        ++groups;
    }

    cout << groups << '\n';
    return 0;
}

[NOIP2007-普及] 纪念品分组

目录

题目描述

思路

参考代码