解题思路
这是一道贪心算法问题,主要思路如下:
-
数据处理:
- 存储每颗糖的饱腹值
- 记录每只小熊的战斗力和饥饿值
- 按战斗力排序确定吃糖顺序
-
贪心策略:
- 战斗力高的小熊优先选择
- 每只小熊选择不超过当前饥饿值的最大糖果
- 一颗糖只能被吃一次
-
实现细节:
- 使用
map
存储小熊的战斗力和饥饿值对应关系 - 使用
vector
存储排序后的战斗力序列 - 动态更新剩余糖果
- 使用
代码
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> candies, bears_power, bears_hunger;
// 读入糖果的饱腹值
for(int i = 0; i < m; i++) {
int p;
cin >> p;
candies.push_back(p);
}
// 读入小熊的战斗力和饥饿值
map<int, int> bear_map;
vector<int> original_order;
for(int i = 0; i < n; i++) {
int power, hunger;
cin >> power >> hunger;
bear_map[power] = hunger;
bears_power.push_back(power);
original_order.push_back(power);
}
// 排序糖果和战斗力
sort(candies.begin(), candies.end(), greater<int>());
sort(bears_power.begin(), bears_power.end(), greater<int>());
// 按战斗力顺序分配糖果
for(int i = 0; i < bears_power.size(); i++) {
auto it = bear_map.find(bears_power[i]);
int hunger = it->second;
int j = 0;
while(j < candies.size()) {
if(candies[j] <= hunger) {
hunger -= candies[j];
candies.erase(candies.begin() + j);
j = 0;
} else {
j++;
}
}
it->second = hunger;
}
// 按原始顺序输出结果
for(int i = 0; i < n; i++) {
cout << bear_map[original_order[i]] << endl;
}
return 0;
}
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
// 读入糖果的饱腹值
ArrayList<Integer> candies = new ArrayList<>();
for(int i = 0; i < m; i++) {
candies.add(sc.nextInt());
}
// 读入小熊的信息
TreeMap<Integer, Integer> bearMap = new TreeMap<>(Collections.reverseOrder());
int[] originalOrder = new int[n];
for(int i = 0; i < n; i++) {
int power = sc.nextInt();
int hunger = sc.nextInt();
bearMap.put(power, hunger);
originalOrder[i] = power;
}
// 排序糖果
Collections.sort(candies, Collections.reverseOrder());
// 分配糖果
for(Map.Entry<Integer, Integer> entry : bearMap.entrySet()) {
int hunger = entry.getValue();
Iterator<Integer> it = candies.iterator();
while(it.hasNext()) {
int candy = it.next();
if(candy <= hunger) {
hunger -= candy;
it.remove();
}
}
bearMap.put(entry.getKey(), hunger);
}
// 输出结果
for(int power : originalOrder) {
System.out.println(bearMap.get(power));
}
}
}
n, m = map(int, input().split())
# 读入糖果的饱腹值
candies = sorted([int(x) for x in input().split()], reverse=True)
# 读入小熊的信息
bears = []
original_order = []
for i in range(n):
power, hunger = map(int, input().split())
bears.append([power, hunger])
original_order.append(power)
# 按战斗力排序
bears.sort(reverse=True, key=lambda x: x[0])
# 分配糖果
bear_map = {}
for power, hunger in bears:
remaining_hunger = hunger
j = 0
while j < len(candies):
if candies[j] <= remaining_hunger:
remaining_hunger -= candies[j]
candies.pop(j)
else:
j += 1
bear_map[power] = remaining_hunger
# 按原始顺序输出结果
for power in original_order:
print(bear_map[power])
算法及复杂度
- 算法:贪心算法
- 时间复杂度:
-
为小熊数量,
为糖果数量
- 空间复杂度:
- 需要存储小熊和糖果的信息