There Is a Convenience Store Below My House
Time limit2sMemory limit1024 MB
Given N stores each labeled with one of M brands, assign each brand to one of M days and find the minimum number of people so every store is watched exactly on its brand's day.
- Level
Medium5 of 10
- Topics
- Greedy, Sorting, Hash map, Implementation
- Solved
- No attempts yet
Problem
This is a problem. Jeonghun told his friends that there is a convenience store below his rented room.
To find Jeonghun's rented room, his friends decided to stake out the area around each of N convenience stores near the Catholic University. There are M convenience store brands, such as 2Mart, SeeYou, CS=25, and MiniGo. Since there are too many convenience stores, the friends decided to pick one brand per day and stake out every store of that brand. Each convenience store needs at least one person staking it out, and since there are M brands, they can stake out all N convenience stores in at least M days. Since they do not know when Jeonghun will show up, they want to make a staking-out schedule for M days. Find the minimum number of people needed so that they can stake out the stores of every brand without missing any.
Input
Two integers N (1 ≤ N ≤ 1,000) and M (1 ≤ M ≤ N) are given.
The next line gives the brand X (1 ≤ X ≤ M) of each of the N convenience stores as integers.
Output
Print the minimum number of people that must gather.