Codeforces 1780 C - Bon Appetit! Tutorial

In this problem, we are given the number of important guests visiting Tonio's hometown of Morioh (n) and the number of tables reserved for them in a restaurant (m). Each guest has their own food preferences, and the ith guest wants only the dish of the type ai. Every guest should be seated at some table, and at table i, no more than ci guests can be seated. The goal is to determine the type of dish xi that will be served at each table, and assign guests to tables in a way that maximizes the number of satisfied guests.

The first step is to count the number of guests who prefer each dish. This can be done using an array of size n+1 and incrementing the ith element of the array for each guest i who prefers dish i.

Next, we need to sort the tables in decreasing order of their capacity. This is because we want to assign guests to tables that can accommodate more guests first, as this will give us more flexibility in assigning guests to other tables.

We also need to sort the dishes in decreasing order of the number of guests who prefer them. This is because we want to assign dishes that are preferred by more guests to tables first, as this will result in more guests being satisfied.

Now, we can iterate over the tables and the dishes simultaneously, and for each table, assign the dish that is currently being considered if there are enough guests who prefer that dish. We also need to decrement the number of guests who prefer that dish, and decrement the capacity of the table.

After assigning the dish to the table, we can then move on to the next table and dish. We can repeat this process until we have assigned all guests to a table.

Once we have assigned all guests, we can count the number of satisfied guests by checking how many guests were assigned to a table that serves their preferred dish.

def bon_appetit(t, test_cases):
    for i in range(t):
        n, m = test_cases[i][:2]
        guests = test_cases[i][2]
        tables = test_cases[i][3]
        dishes = [0] * n
        for j in range(n):
            dishes[guests[j] - 1] += 1
        table_index = 0
        guest_count = 0
        for j in range(n):
            while dishes[j] > 0 and table_index < m:
                if tables[table_index] > 0:
                    guests_at_table = min(tables[table_index], dishes[j])
                    tables[table_index] -= guests_at_table
                    dishes[j] -= guests_at_table
                    guest_count += guests_at_table
                table_index += 1

t = int(input())
test_cases = []
for i in range(t):
    n, m = map(int, input().split())
    guests = list(map(int, input().split()))
    tables = list(map(int, input().split()))
    test_cases.append([n, m, guests, tables])
bon_appetit(t, test_cases)