问题理解

问题描述：

Moo U 的自助餐厅没有干草了，因此需要为 C 头小牛订购披萨。Pizza Farm 是一个当地披萨店，可以按照要求制作披萨，但有以下限制：

1. 每块披萨必须包含恰好 K 种配料。
2. 每种配料在一块披萨上不能重复。
3. 没有两块披萨可以有相同的配料组合。

每头小牛只吃自己喜欢的配料都包含的披萨。我们的目标是确定最多可以喂饱多少头小牛。

输入：

• 第一行包含三个整数 C, T, K，分别表示小牛数量、配料数量和每块披萨的配料数量。
• 接下来的 C 行，每行描述一头小牛喜欢的配料，第一个数字是小牛喜欢的配料数量，后面是这些配料的编号。

输出：

• 一个整数，表示最多可以喂饱的小牛数量。

解决思路

为了最大化喂饱的小牛数量，我们需要选择披萨的配料组合，使得尽可能多的小牛喜欢这些配料组合。

1. 配料重要性排序：

   • 统计每种配料被多少小牛喜欢。配料被越多小牛喜欢，重要性越高。

2. 选择最重要的 K 种配料：

   • 选择被最多小牛喜欢的 K 种配料组成披萨。

3. 计算喂饱的小牛数量：

   • 使用选定的披萨组合，计算能喂饱的小牛数量。

代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int C, T, K;
    cin >> C >> T >> K;

    vector<vector<int>> cows(C);
    for (int i = 0; i < C; ++i) {
        int num;
        cin >> num;
        cows[i].resize(num);
        for (int j = 0; j < num; ++j) {
            cin >> cows[i][j];
            cows[i][j]--; 
        }
    }

   
    vector<int> ingredient_count(T, 0);
    for (int i = 0; i < C; ++i) {
        for (int ingredient : cows[i]) {
            ingredient_count[ingredient]++;
        }
    }

   
    vector<pair<int, int>> sorted_ingredients;
    for (int i = 0; i < T; ++i) {
        sorted_ingredients.emplace_back(ingredient_count[i], i);
    }
    sort(sorted_ingredients.rbegin(), sorted_ingredients.rend());

   
    int pizza_mask = 0;
    for (int i = 0; i < K; ++i) {
        pizza_mask |= (1 << sorted_ingredients[i].second);
    }

    
    int max_cows = 0;
    for (int i = 0; i < C; ++i) {
        bool all_liked = true;
        for (int ingredient : cows[i]) {
            if (!(pizza_mask & (1 << ingredient))) {
                all_liked = false;
                break;
            }
        }
        if (all_liked) {
            max_cows++;
        }
    }

    cout << max_cows << endl;

    return 0;
}

总结

通过选择被最多小牛喜欢的 K 种配料，我们能够高效地找到一个披萨组合，喂饱最多的小牛。这种方法避免了枚举所有披萨组合，从而显著降低了时间复杂度。