BootsExchange
SRM 307 · 2006-06-14 · by Mike Mirzayanov
Problem Statement
A boot shop has received a shipment from the factory consisting of N left boots and N right boots. Each boot has some integer size, and a left and right boot will form a proper pair if they have equal sizes. Each boot can only belong to a single pair. The employees of the boot store want to create N proper pairs of boots. Fortunately, the factory has offered to exchange any number of boots in the shipment with new boots of different sizes.
You are given a
Constraints
- Each element in left will be between 1 and 1000, inclusive.
- Each element in right will be between 1 and 1000, inclusive.
- left and right will have the same number of elements.
- left will contain between 1 and 50 elements, inclusive.
{1, 3, 1}
{2, 1, 3}
Returns: 1
They can exchange a size 1 left shoe for a size 2 left shoe, or they can exchange the size 2 right shoe for a size 1 right shoe.
{1, 3}
{2, 2}
Returns: 2
They can exchange both left shoes for size 2 left shoes, or they can exchange the right shoes for a size 1 right shoe and a size 3 right shoe, or they can mix these two possibilities.
{1, 2, 3, 4, 5, 6, 7}
{2, 4, 6, 1, 3, 7, 5}
Returns: 0
Nothing to exchange.
{3, 1, 4, 7, 3, 1, 4, 5, 1}
{2, 5, 2, 3, 4, 1, 4, 6, 8}
Returns: 4
{5, 2, 1, 4, 7, 9, 1, 1, 3, 4}
{2, 5, 1, 3, 4, 6, 3, 2, 2, 5}
Returns: 5
Submissions are judged against all 122 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BootsExchange with a public method int leastAmount(vector<int> left, vector<int> right) · 122 test cases · 2 s / 256 MB per case