#P4478. 第2题-一顿大餐的菜品选择方式
-
1000ms
Tried: 12
Accepted: 7
Difficulty: 6
所属公司 :
华为
时间 :2025年11月19日-非AI方向(通软&嵌软&测试&算法&数据科学)
-
算法标签>暴力枚举
第2题-一顿大餐的菜品选择方式
解题思路
你要在食堂的菜品中各选出一份 全票菜(type=1)、半票菜(type=2)、素菜(type=3), 要求这三份菜里出现的食材编号不能有重复。每个菜最多 4 种食材,0 表示没有食材。
输入给出了 N 个菜:
ID, T, D1, D2, D3, D4
ID为菜品编号T为菜品类型 1/2/3D1..D4为这道菜的食材编号(>0 有效,0 表示空)
输出:所有满足要求的三菜组合列表,每行
全票菜ID 半票菜ID 素菜ID
排序规则为:
- 先按全票菜 ID 升序
- 若相同,再按半票菜 ID 升序
- 若还相同,再按素菜 ID 升序
若不存在任何合法组合,输出
-1。
核心算法(暴力枚举 + 分类)
-
读入所有菜品,按类型分成三组:
full(全票)、half(半票)、veg(素菜)。 -
对每个菜,只保留非 0 的食材,存成一个小数组 / 向量。
-
暴力枚举三重循环:
- 枚举全票菜
F - 枚举半票菜
H - 枚举素菜
V
- 枚举全票菜
-
对当前三道菜,检查食材是否两两有交集:
-
写一个函数
share(A, B),如果两菜的任意一个食材编号相同,则返回 true。 -
组合合法当且仅当:
!share(F, H) && !share(F, V) && !share(H, V)
-
-
对于每个合法组合,把
(F.id, H.id, V.id)加入答案数组。 -
对答案数组按字典序排序(即按上面的三重关键字排序)。
-
按顺序输出所有组合;若数组为空,输出
-1。
由于每道菜最多 4 个食材,检查两菜是否冲突最多比较 16 次,常数很小,直接暴力足够。
复杂度分析
设全票菜数量为 A,半票菜数量为 B,素菜数量为 C,总菜数 N ≤ 100。
- 三重枚举:
O(A * B * C),最坏情况下A, B, C都是O(N),复杂度O(N^3)。 - 每次冲突检查是常数级(最多 16 次比较)。
所以总体时间复杂度 O(N^3)(这里 N ≤ 100,可以轻松通过)。
空间复杂度:只存菜品和所有答案,都是 O(N + 答案数量),在数据范围内完全可行。
代码实现
Python
import sys
# 菜品结构:id, type, ingredients(只保存非0食材)
class Dish:
def __init__(self, did, tp, ing):
self.id = did
self.tp = tp
self.ing = ing
# 判断两道菜是否有相同食材
def share(d1, d2):
for x in d1.ing:
for y in d2.ing:
if x == y:
return True
return False
# 核心功能:返回所有合法组合 (fid, hid, vid)
def solve(dishes):
full = []
half = []
veg = []
# 按类型分类
for d in dishes:
if d.tp == 1:
full.append(d)
elif d.tp == 2:
half.append(d)
elif d.tp == 3:
veg.append(d)
res = []
# 三重枚举所有组合
for f in full:
for h in half:
if share(f, h): # 先剪枝:全票与半票冲突则跳过
continue
for v in veg:
# 三两两不冲突才是合法组合
if share(f, v) or share(h, v):
continue
res.append((f.id, h.id, v.id))
# 按 (全票ID, 半票ID, 素菜ID) 升序排序
res.sort()
return res
def main():
data = list(map(int, sys.stdin.read().split()))
if not data:
return
it = iter(data)
n = next(it)
dishes = []
# 读取所有菜品
for _ in range(n):
did = next(it)
tp = next(it)
tmp_ing = [next(it) for _ in range(4)]
ing = [x for x in tmp_ing if x > 0] # 去掉为0的占位
dishes.append(Dish(did, tp, ing))
ans = solve(dishes)
out_lines = []
if not ans:
out_lines.append("-1\n")
else:
for fid, hid, vid in ans:
out_lines.append(f"{fid} {hid} {vid}\n")
sys.stdout.write("".join(out_lines))
if __name__ == "__main__":
main()
Java
import java.util.*;
// ACM 风格主类
public class Main {
// 菜品结构
static class Dish {
int id; // 菜品编号
int type; // 菜品类型 1/2/3
int[] ing; // 有效食材列表(不含0)
Dish(int id, int type, int[] ing) {
this.id = id;
this.type = type;
this.ing = ing;
}
}
// 判断两道菜是否有相同食材
static boolean share(Dish a, Dish b) {
for (int x : a.ing) {
for (int y : b.ing) {
if (x == y) {
return true;
}
}
}
return false;
}
// 核心功能:返回所有合法组合
static List<int[]> solve(List<Dish> dishes) {
List<Dish> full = new ArrayList<>();
List<Dish> half = new ArrayList<>();
List<Dish> veg = new ArrayList<>();
// 按类型分类
for (Dish d : dishes) {
if (d.type == 1) {
full.add(d);
} else if (d.type == 2) {
half.add(d);
} else if (d.type == 3) {
veg.add(d);
}
}
List<int[]> res = new ArrayList<>();
// 三重枚举所有组合
for (Dish f : full) {
for (Dish h : half) {
if (share(f, h)) { // 先检查这两道菜
continue;
}
for (Dish v : veg) {
if (share(f, v) || share(h, v)) {
continue;
}
res.add(new int[]{f.id, h.id, v.id});
}
}
}
// 按 (全票ID, 半票ID, 素菜ID) 排序
Collections.sort(res, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
if (a[0] != b[0]) {
return a[0] - b[0];
}
if (a[1] != b[1]) {
return a[1] - b[1];
}
return a[2] - b[2];
}
});
return res;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
if (!sc.hasNextInt()) {
return; // 无输入直接结束
}
int n = sc.nextInt();
List<Dish> dishes = new ArrayList<>();
// 读取n个菜品
for (int i = 0; i < n; i++) {
int id = sc.nextInt();
int type = sc.nextInt();
int[] tmp = new int[4];
for (int j = 0; j < 4; j++) {
tmp[j] = sc.nextInt();
}
// 过滤掉0,只保留真正的食材
int cnt = 0;
for (int x : tmp) {
if (x > 0) {
cnt++;
}
}
int[] ing = new int[cnt];
int idx = 0;
for (int x : tmp) {
if (x > 0) {
ing[idx++] = x;
}
}
dishes.add(new Dish(id, type, ing));
}
List<int[]> ans = solve(dishes);
if (ans.isEmpty()) {
System.out.println("-1");
} else {
for (int[] arr : ans) {
System.out.println(arr[0] + " " + arr[1] + " " + arr[2]);
}
}
sc.close();
}
}
C++
#include <bits/stdc++.h>
using namespace std;
// 菜品结构体
struct Dish {
int id; // 菜品编号
int type; // 菜品类型 1/2/3
vector<int> ing; // 食材列表(不含0)
};
// 判断两道菜是否有相同食材
bool share(const Dish &a, const Dish &b) {
for (int x : a.ing) {
for (int y : b.ing) {
if (x == y) return true;
}
}
return false;
}
// 核心功能:返回所有合法组合
vector<tuple<int,int,int>> solve(const vector<Dish> &dishes) {
vector<Dish> full, half, veg;
// 按类型分类
for (const auto &d : dishes) {
if (d.type == 1) full.push_back(d);
else if (d.type == 2) half.push_back(d);
else if (d.type == 3) veg.push_back(d);
}
vector<tuple<int,int,int>> res;
// 三重枚举所有组合
for (const auto &f : full) {
for (const auto &h : half) {
if (share(f, h)) continue; // 先剪枝
for (const auto &v : veg) {
if (share(f, v) || share(h, v)) continue;
res.emplace_back(f.id, h.id, v.id);
}
}
}
// 默认按 (first, second, third) 字典序排序
sort(res.begin(), res.end());
return res;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
if (!(cin >> n)) {
return 0; // 无输入
}
vector<Dish> dishes;
dishes.reserve(n);
// 读取所有菜品
for (int i = 0; i < n; ++i) {
int id, type;
cin >> id >> type;
vector<int> ing;
for (int j = 0; j < 4; ++j) {
int x;
cin >> x;
if (x > 0) ing.push_back(x); // 丢弃0
}
dishes.push_back(Dish{id, type, ing});
}
vector<tuple<int,int,int>> ans = solve(dishes);
if (ans.empty()) {
cout << -1 << "\n";
} else {
for (auto &t : ans) {
int fid, hid, vid;
tie(fid, hid, vid) = t;
cout << fid << " " << hid << " " << vid << "\n";
}
}
return 0;
}
题目内容
你来到食堂想大吃一顿。你将在全荤、半荤、素中各挑选一种菜品,且所挑选菜品的食材不能重复,请你计算 菜品选择方式
输入描述
食堂的所有餐线的菜单 第1行是:N,其中N为所有菜品数量,范围(0,100]
第2行是:ID1 T1 DI1 DI2 DI3 DI4,其中ID1:为第1个菜品的菜品名,范围(0,100]。T1为菜品类型,1表示全荤、2表示半荤、3表示素。DI1...DI4分别为第1个菜品的第1种到第4种食材,食材不会重复,范围[0,100],0表示占位,无食材。
第N+1行是:IDN TN DN1 DN2 DN3 DN4,其中IDN为第N个菜品的菜品名。TN为菜品类型。DN1...DN4分别为第N个菜品的第1种到第4种食材
输出描述
菜品选择的所有方式列表,列表优先按照全荤菜品名升序排序,其次半荤菜品名升序排序,再次兼菜品名升序 排序 每行格式:全荤菜品名 半荤菜品名 素菜品名
无法选择请输出−1
样例1
输入
1
1 1 1 2 3 4
输出
-1
说明
仅有1个菜,无法按要求挑选
样例2
输入
6
2 2 5 6 7 8
3 3 9 10 11 12
4 2 1 2 3 0
5 1 5 0 7 8
1 1 1 2 3 4
6 1 1 2 3 4
输出
1 2 3
5 4 3
6 2 3
说明
总共有6种菜品。
菜品名2,半荤,食材5、6、7、8
菜品名3,素,食材9、10、11、12
菜品名4,半荤,食材1、2、3
菜品名5,全荤,食材5、7、8
菜品名1,全荤,食材1、2、3、4
菜品名6,全荤,食材1、2、3、4
菜品1、菜品4、菜品6食材有相同的部分,不能同时选择。
菜品2和菜品5食材有相同的部分,不能同时选择。
可选择的方式有5+4+3,1+2+3,6+2+3 3种。且根据升序排序要求输出 1 2 3 5 4 3 6 2 3
样例3
输入
4
1 1 1 2 3 4
2 2 5 6 7 8
3 3 9 10 11 12
4 2 13 14 15 16
输出
1 2 3
1 4 3
说明
总共有4种菜品
菜品名1,全荤,食材1、2、3、4
菜品名2,半荤,食材5、6、7、8
菜品名3,素,食材9、10、11、12
菜品名4,半荤,食材13、14、15、16
由于食材都不重复。
可选择的方式有1+2+3,1+4+3 2种
提示
由于中餐的博大精深。 同样的食材选择可做出不同的菜品。但同一个菜品名一定是同样的食材