题面描述

H餐饮公司为了增加销量，推出多种套餐，每种套餐由一种主食和若干小食或饮料组成。公司在国庆节期间需要从所有套餐中选择指定数量的套餐参加促销活动，选择时需要遵循以下策略：

1. 优先选择成本低的套餐；
2. 如果成本相同，则优先选择利润较高的；
3. 如果成本和利润都相同，则优先选择套餐索引较小的；
4. 主食有数量限制的情况下，不能超过其限制数量；没有限制的主食则不限数量。

思路

模拟题，用一个结构体存每道菜的$id$,成本，价格，索引，再用一个数组存每个$id$的限制，按照题目要求对每道菜排序后遍历一遍，按照有无限制分类算贡献即可，如果最后安排的套餐等于给定的需求量，则升序输出答案即可。

具体实现

1. 数据读取与存储：

   • 读取所有套餐的信息，存储为一个结构体或类，包含主食ID、成本、利润和索引。
   • 读取主食的限制信息，使用一个哈希表（如unordered_map）来记录每种主食的选择上限。

2. 排序：

   • 对所有套餐按照以下优先级进行排序：
     • 成本从低到高；
     • 成本相同的情况下，利润从高到低；
     • 成本和利润相同的情况下，索引从小到大。

3. 选择套餐：

   • 遍历排序后的套餐列表，依次选择符合主食限制的套餐。
   • 对于有主食限制的套餐，记录已选择的数量，确保不超过上限。
   • 如果选择的套餐数量达到要求，记录所选套餐的索引。
   • 如果遍历完所有套餐后仍未达到要求，返回-1。

4. 结果输出：

   • 如果成功选择到指定数量的套餐，按照升序排列输出它们的索引；
   • 否则，输出-1。

cpp

#include <bits/stdc++.h>
using namespace std;

// 定义套餐结构体
struct Package {
    int mainID;    // 主食ID
    int cost;      // 成本
    int profit;    // 利润
    int index;     // 套餐索引
};

// 自定义排序规则
bool cmp(const Package &a, const Package &b) {
    if (a.cost != b.cost)
        return a.cost < b.cost;           // 成本低的优先
    if (a.profit != b.profit)
        return a.profit > b.profit;       // 利润高的优先
    return a.index < b.index;             // 索引小的优先
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int M;
    cin >> M;
    vector<Package> packages(M);
    for(int i = 0; i < M; ++i){
        cin >> packages[i].mainID >> packages[i].cost >> packages[i].profit;
        packages[i].index = i;
    }
    
    int N;
    cin >> N;
    unordered_map<int, int> limitMap;
    for(int i = 0; i < N; ++i){
        int id, limit;
        cin >> id >> limit;
        limitMap[id] = limit;
    }
    
    int NUM;
    cin >> NUM;
    
    // 按照自定义规则排序
    sort(packages.begin(), packages.end(), cmp);
    
    vector<int> selected;
    // 记录每种主食已选择的数量
    unordered_map<int, int> selectedMap;
    
    for(auto &pkg : packages){
        // 检查主食是否有选择限制
        if(limitMap.find(pkg.mainID) != limitMap.end()){
            if(selectedMap[pkg.mainID] < limitMap[pkg.mainID]){
                selected.push_back(pkg.index);
                selectedMap[pkg.mainID]++;
            }
        }
        else{
            // 没有限制，直接选择
            selected.push_back(pkg.index);
        }
        if(selected.size() == NUM)
            break;
    }
    
    if(selected.size() == NUM){
        sort(selected.begin(), selected.end());
        for(int i = 0; i < selected.size(); ++i){
            if(i != 0) cout << ' ';
            cout << selected[i];
        }
        cout << '\n';
    }
    else{
        cout << "-1\n";
    }
    
    return 0;
}

python

# 定义套餐类，包含套餐 id、套餐类型 pid、成本 cost 和利润 profit
class Package:
    def __init__(self, id, pid, cost, profit):
        self.id = id          # 套餐 id
        self.pid = pid        # 套餐类型 id
        self.cost = cost      # 成本
        self.profit = profit  # 利润

# 读入总套餐数
m = int(input())

# 初始化套餐列表和限制字典
packages = []  # 存储所有套餐对象
limit = {}     # 每种套餐类型的可用数量限制

# 读取每个套餐的详细信息
for i in range(m):
    # 读取套餐类型 pid、成本 cost 和利润 profit
    pid, cost, profit = map(int, input().split())
    # 创建套餐对象并加入列表
    packages.append(Package(i, pid, cost, profit))
    # 默认每种类型的可用数量为一个较大的值（即无限制）
    limit[pid] = 10 ** 9

# 读入指定的有限制的套餐类型数量
n = int(input())
for _ in range(n):
    # 读取限制类型 id 和数量 num
    id, num = map(int, input().split())
    # 更新限制字典中的可用数量
    limit[id] = num

# 目标要选的套餐数量
num = int(input())

# 按指定规则对套餐进行排序
# 排序规则：先按成本从小到大，其次按利润从大到小，最后按套餐类型 pid
packages.sort(key=lambda x: (x.cost, -x.profit, x.pid))

# 初始化结果列表用于存储最终选择的套餐 id
res_id = []

# 遍历排序后的套餐列表
for i in range(m):
    # 检查套餐类型是否在限制字典中且有剩余数量
    if packages[i].pid in limit and limit[packages[i].pid] > 0:
        # 记录选择的套餐 id
        res_id.append(packages[i].id)
        # 减少该类型套餐的剩余数量
        limit[packages[i].pid] -= 1
    # 如果已选择的套餐数量达到目标数量，则退出循环
    if len(res_id) == num:
        break

# 对选择的套餐 id 进行排序
res_id.sort()

# 检查是否成功选择到目标数量的套餐
if len(res_id) != num:
    # 若未达到目标数量，输出 -1
    print(-1)
else:
    # 若达到目标数量，输出选择的套餐 id
    print(" ".join(map(str, res_id)))

java

import java.util.*;
import java.io.*;

public class Main {
    // 定义套餐类
    static class Package {
        int mainID;
        int cost;
        int profit;
        int index;
        
        Package(int mainID, int cost, int profit, int index){
            this.mainID = mainID;
            this.cost = cost;
            this.profit = profit;
            this.index = index;
        }
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        // 读取套餐数量
        int M = Integer.parseInt(br.readLine());
        List<Package> packages = new ArrayList<>();
        for(int i =0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int mainID = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            int profit = Integer.parseInt(st.nextToken());
            packages.add(new Package(mainID, cost, profit, i));
        }
        
        // 读取限制数量
        int N = Integer.parseInt(br.readLine());
        Map<Integer, Integer> limitMap = new HashMap<>();
        for(int i =0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            int id = Integer.parseInt(st.nextToken());
            int limit = Integer.parseInt(st.nextToken());
            limitMap.put(id, limit);
        }
        
        // 读取需要选择的套餐数量
        int NUM = Integer.parseInt(br.readLine());
        
        // 自定义排序
        Collections.sort(packages, new Comparator<Package>(){
            public int compare(Package a, Package b){
                if(a.cost != b.cost)
                    return a.cost - b.cost;          // 成本升序
                if(a.profit != b.profit)
                    return b.profit - a.profit;      // 利润降序
                return a.index - b.index;            // 索引升序
            }
        });
        
        List<Integer> selected = new ArrayList<>();
        Map<Integer, Integer> selectedMap = new HashMap<>();
        
        for(Package pkg : packages){
            if(limitMap.containsKey(pkg.mainID)){
                if(selectedMap.getOrDefault(pkg.mainID, 0) < limitMap.get(pkg.mainID)){
                    selected.add(pkg.index);
                    selectedMap.put(pkg.mainID, selectedMap.getOrDefault(pkg.mainID, 0) +1);
                }
            }
            else{
                selected.add(pkg.index);
            }
            if(selected.size() == NUM)
                break;
        }
        
        if(selected.size() == NUM){
            Collections.sort(selected);
            StringBuilder sb = new StringBuilder();
            for(int i =0; i < selected.size(); i++){
                if(i !=0) sb.append(' ');
                sb.append(selected.get(i));
            }
            System.out.println(sb.toString());
        }
        else{
            System.out.println("-1");
        }
    }
}

题目内容

$H$餐饮公司为增加销量，以一种主打食物搭配其他若干种小食或饮料，组成一种套餐来销售。例如

$0$:牛肉汉堡+薯条+可乐;

$1$:牛肉汉堡+鸡翅+可乐;

$2$:牛肉饭+鸡翅+牛肉汤

公司为了国庆节的促销活动，提供了如下信息:

$1$.每种套餐的主食$ID$以及套餐成本、利润等信息，表示为[主食$ID$,套餐成本,套餐利润];

$2$.主食是有限制的，表示为[主食$ID$,选择数量上限]，如$100\ 1$，意味着以$100$为主食的套餐仅有一份。

$3$.小食没有限制。

$4$.所有套餐信息，按行描述，套餐从0开始索引。 现在要为公司选出指定数量$NUM$款套餐参加国庆节的促销活动，具体选择策略如下:

1.优先选择成本低的套餐;

2.如果成本相同，则优先选择利润较高的;

3.如果成本相同，利润也相同，则优先选择套餐索引小的;

4.给出限制的主食不能超过其支持的限制数量，没有给出限制的主食不限制数量。

如果能成功选出$NUM$款套餐，则返回它们的套餐索引集合，并按照从小到大排列，否则返回$-1$。

输入描述

第一行一个整数$M$，表示套餐的数量，取值范围[$1,10000$]。

接下来$M$行，每行代表一款套餐，套餐索引从$0$开始，每行三个整数，分别表示主食$ID$，成本，利润。

接下来一行一个整数$N$，表示限制$limit$的数量，取值范围[$1,10000$]。

接下来$N$行，每行两个整数，分别表示主食$ID$，限制数量。

最后一行一个整数$NUM$，表示推出套餐的数量，取值范围[$1,10000$]。

其中主食$ID$，成本，利润，取值范围也都为[$1,10000$]

输出描述

购买的套餐索引，升序排列，如果不能则返回$-1$。

样例1

输入

6
100 30 10
200 10 10
100 50 20
200 10 10
400 20 20
200 20 10
3 
100 1
200 1
400 2
3

输出

0 1 4

说明

公司推出$6$种套餐组合，索引从$0-5$。

按排序规则，优先选择成本为$10$的套餐，利润一样,按索引排序为索引$1$即[$200\ 10\ 10$]，索引$3$即[$200\ 10\ 10$]。

成本$20$的套餐，按利润排序为索引$4$，索引$5$。

成本$30$的套餐，索引$0$。成本$50$的套餐，索引$2$。

最后根据限制条件主食$200、100$的套餐限制为$1$款，输出结果按照套餐索引升序排列$0\ 1\ 4$。

样例2

输入

3
100 30 10 
200 10 10
100 50 20
2
100 1
200 1
3

输出

-1

说明

由于$100,200$的限制都为$1$，所以只能选择两款套餐，数量不足，返回$-1$