PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
None
PROBLEM:
Chef sells N types of donuts. He has A_i of the i-th type of donut.
There are M customers. Customer i wants one of donut type B_i.
How many customers will be unsatisfied?
EXPLANATION:
This is a simple simulation task.
Let \text{ans} denote the number of people who are sad.
Initially, \text{ans} = 0.
For each i from 1 to M,
- If A_{B_i} = 0, there are no more donuts of type B_i remaining. So, person i will be sad.
In this case, increment \text{ans} by 1. - If instead A_{B_i} \gt 0, then this person will be satisfied.
Since they take one donut, decrement A_{B_i} by one.
The final value of \text{ans} is the answer.
TIME COMPLEXITY:
\mathcal{O}(N+M) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
sad = 0
for x in b:
if a[x-1] == 0: sad += 1
else: a[x-1] -= 1
print(sad)