#P3845. 第2题-奖项设置
-
1000ms
Tried: 537
Accepted: 111
Difficulty: 5
所属公司 :
华为
时间 :2025年9月28日-非AI方向(通软&嵌软&测试&算法&数据科学)
-
算法标签>贪心其他二分查找
第2题-奖项设置
解题思路
-
将每个“奖项”看成一个容量为
limit的“箱子”,每个奖品是一件物品,价值即体积。 -
题目给定的获奖者策略是:在不超过
limit的前提下优先选择价值最高的奖品并持续选择,直到无法再选。 这与我们按同样的规则把物品装进箱子完全一致,因此问题等价为:用“在剩余容量内每次放入当前能放的最大物品”的贪心规则进行装箱,所需箱子(奖项)的最少个数。 -
实现方法:
- 先对所有价值做计数并保持有序(如
multiset/TreeMap或“排序 + 计数”)。 - 每开启一个奖项(箱子),设剩余容量
rem = limit; - 反复在有序容器中查找
<= rem的最大值(upper_bound/floorKey),取出一件、减少rem,直到找不到可放的奖品; - 计数 +1,继续下一奖项;
- 直到所有奖品被取完。
- 先对所有价值做计数并保持有序(如
-
相关算法:贪心 + 有序多重集合(上/下界查找)。该策略与题目给定的选择规则一致,且总取件数为
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<=104 ;
第二行:正整数数组 values,长度为 len,其中 values[i] 表示第 i 个奖品的价值,1<=values[i]<=104 ;
第三行:正整数 limit ,表示每个获奖者可以获得的最大奖品价值,1<=limit<=104 。
输出描述
整数,代表本次抽奖活动可以设置最少的奖项数量;
样例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 个奖项才能满足所有获奖者的领取诉求