解题思路

• 将每个“奖项”看成一个容量为 limit 的“箱子”，每个奖品是一件物品，价值即体积。

• 题目给定的获奖者策略是：在不超过 limit 的前提下优先选择价值最高的奖品并持续选择，直到无法再选。 这与我们按同样的规则把物品装进箱子完全一致，因此问题等价为：用“在剩余容量内每次放入当前能放的最大物品”的贪心规则进行装箱，所需箱子（奖项）的最少个数。

• 实现方法：

  1. 先对所有价值做计数并保持有序（如 multiset/TreeMap 或“排序 + 计数”）。
  2. 每开启一个奖项（箱子），设剩余容量 rem = limit；
  3. 反复在有序容器中查找 <= rem 的最大值（upper_bound/floorKey），取出一件、减少 rem，直到找不到可放的奖品；
  4. 计数 +1，继续下一奖项；
  5. 直到所有奖品被取完。

• 相关算法：贪心 + 有序多重集合（上/下界查找）。该策略与题目给定的选择规则一致，且总取件数为 n，每次查找/删除为 O(log U)（U 为不同价值的种类数），整体高效。

复杂度分析

• 排序/建表：O(n log n) 或 O(n + U log U)（使用计数+有序键）。
• 每件物品至多被查找并删除一次：O(n log U)。
• 总时间复杂度：O(n log n)（上界）。
• 空间复杂度：O(U)（存放不同价值的计数）。

代码实现

Python

# -*- coding: utf-8 -*-
# 题意功能放在外部函数里；主函数只负责输入输出（ACM 风格）
import sys
from bisect import bisect_right
from collections import Counter
import ast

def min_awards(values, limit):
    """
    在每个奖项容量为 limit 的前提下，
    每次在剩余容量内优先选择价值最高的奖品，问最少需要多少个奖项
    """
    # 题面默认数据合法；若有大于 limit 的物品则无法放入，这里直接忽略/也可假定不存在
    values = [v for v in values if v <= limit]
    if not values:
        return 0

    cnt = Counter(values)                 # 统计每个价值出现次数
    uniq = sorted(cnt.keys())             # 升序唯一值，配合 bisect 查找 <= rem 的最大值
    total = len(values)
    ans = 0

    while total > 0:
        rem = limit
        while True:
            # 找到 <= rem 的最大价值的下标
            idx = bisect_right(uniq, rem) - 1
            # 跳过计数为 0 的键
            while idx >= 0 and cnt[uniq[idx]] == 0:
                idx -= 1
            if idx < 0:                   # 本奖项放不下更多
                break
            val = uniq[idx]
            cnt[val] -= 1                 # 取出一件
            total -= 1
            rem -= val                    # 更新剩余容量
        ans += 1                           # 开启下一个奖项

    return ans

def main():
    data = sys.stdin.read().strip().splitlines()
    if not data:
        return
    n = int(data[0].strip())

    # 第二行既可能是空格分隔的数字，也可能是 Python 列表；优先尝试 literal_eval
    vals_line = data[1].strip()
    values = None
    try:
        parsed = ast.literal_eval(vals_line)
        # 若 literal_eval 得到的是单个数字或列表，统一转成列表
        if isinstance(parsed, (list, tuple)):
            values = [int(x) for x in parsed]
        else:
            values = [int(parsed)]
    except Exception:
        values = list(map(int, vals_line.split()))
    # 只取前 n 个（若输入多给了）
    values = values[:n]

    limit = int(data[2].strip())
    print(min_awards(values, limit))

if __name__ == "__main__":
    main()

Java

// ACM 风格：类名 Main，主函数负责 IO，核心逻辑在外部静态函数中
import java.util.*;

public class Main {

    // 在剩余容量内优先选择最大价值的贪心装箱
    public static int solve(int[] a, int limit) {
        // 使用 TreeMap 作为有序多重集合：key=价值, value=计数
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int total = 0;
        for (int v : a) {
            if (v <= limit) { // 默认输入合法，若存在>limit，这里忽略
                map.put(v, map.getOrDefault(v, 0) + 1);
                total++;
            }
        }
        if (total == 0) return 0;

        int ans = 0;
        while (total > 0) {
            int rem = limit;
            while (true) {
                // floorKey(rem): 找到 <= rem 的最大键
                Integer key = map.floorKey(rem);
                if (key == null) break; // 本奖项装不进更多
                // 取出一件
                int c = map.get(key);
                if (c == 1) map.remove(key);
                else map.put(key, c - 1);
                total--;
                rem -= key;
            }
            ans++; // 开启下一个奖项
        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in); // 数据范围较小，默认不用快读
        if (!sc.hasNextInt()) return;
        int n = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = sc.nextInt();
        int limit = sc.nextInt();
        System.out.println(solve(a, limit));
        sc.close();
    }
}

C++

// ACM 风格：主函数读写，求解函数在外部
#include <bits/stdc++.h>
using namespace std;

// 使用 multiset 作为有序多重集合：每次取 <= rem 的最大值
int solve(vector<int>& a, int limit) {
    multiset<int> ms;
    for (int v : a) {
        if (v <= limit) ms.insert(v); // 默认输入合法；若有 >limit 的奖品则忽略
    }
    if (ms.empty()) return 0;

    int ans = 0;
    while (!ms.empty()) {
        int rem = limit;
        while (true) {
            // upper_bound(rem) 返回第一个 > rem 的迭代器，往前一步即 <= rem 的最大值
            auto it = ms.upper_bound(rem);
            if (it == ms.begin()) break; // 没有可放的
            --it;                        // 取 <= rem 的最大值
            rem -= *it;                  // 更新剩余容量
            ms.erase(it);                // 删除该元素一份
        }
        ans++; // 一个奖项装满（或无法继续装）
    }
    return ans;
}

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

    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    int limit;
    cin >> limit;

    cout << solve(a, limit) << "\n";
    return 0;
}

题目内容

部门准备了一批奖品用于举办抽奖活动，奖品的价值为给定的正整数数组 $values$，其中 $values[i]$ 表示第 $i$ 个奖品的价值。

每位获奖者可以选择不限个数最大价值 $limit$ 的奖品组合，获奖者选择奖品的策略为在 $limit$ 限制内优先选择单价最高的奖品，请计算最少可以设置多少个奖项；

输入描述

第一行：正整数 $len$ ，表述奖品价值数组 $values$ 的长度，$1<=len<=10^4$ ；

第二行：正整数数组 $values$，长度为 $len$，其中 $values[i]$ 表示第 $i$ 个奖品的价值，$1<=values[i]<=10^4$ ；

第三行：正整数 $limit$ ，表示每个获奖者可以获得的最大奖品价值，$1<=limit<=10^4$ 。

输出描述

整数，代表本次抽奖活动可以设置最少的奖项数量；

样例1

输入

2
1 2
3

输出

1

说明

获奖者选择价值为 $1$ 和 $2$ 的两个奖品，最少可以设置 $1$ 个奖项

样例2

输入

7
13 4 4 3 3 5 5
12

输出

3

说明

获奖者 $1$ 选取价值为 $(5,5)$ 的奖品组合，获奖者 $2$ 选取价值为 $(4,4,3)、3$ 的奖品组合，因此：最少可以设置 $3$ 个奖项才能满足所有获奖者的领取诉求