解题思路

这是一道贪心算法问题,主要思路如下:

  1. 数据处理:

    • 存储每颗糖的饱腹值
    • 记录每只小熊的战斗力和饥饿值
    • 按战斗力排序确定吃糖顺序
  2. 贪心策略:

    • 战斗力高的小熊优先选择
    • 每只小熊选择不超过当前饥饿值的最大糖果
    • 一颗糖只能被吃一次
  3. 实现细节:

    • 使用 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])

算法及复杂度

  • 算法:贪心算法
  • 时间复杂度: - 为小熊数量, 为糖果数量
  • 空间复杂度: - 需要存储小熊和糖果的信息