Connection Status:
Competition Arena > WinterAndMandarins

WinterAndMandarins

SRM 601 · 2013-06-25 · by Witaliy

SRM 601 · 2013-06-25 · by Witaliy · Brute Force, Greedy
Class Name: WinterAndMandarins
Return Type: int
Method Name: getNumber
Arg Types: (vector<int>, int)
Problem Statement

Problem Statement

It's winter time! Time to eat a lot of mandarins with your friends.

You have several bags with mandarins. You are given an int[] bags. For each i, the i-th element of bags represents the number of mandarins in the i-th bag. You are also given an int K. You want to choose exactly K bags and distribute them among you and your friends. To be as fair as possible, you want to minimize the difference between the chosen bag with most mandarins and the chosen bag with fewest mandarins. Return the smallest difference that can be achieved.

Constraints

  • bags will contain between 2 and 50 elements, inclusive.
  • Each element of bags will be between 1 and 1,000,000,000, inclusive.
  • K will be between 2 and N, inclusive, where N is the number of elements in bags.
Examples
0)
{10, 20, 30}
2
Returns: 10

There are three ways to choose two bags in this case: {10, 20}, {20, 30}, and {10, 30}. Both in the first case and in the second case the difference between the largest and the smallest number of mandarins is 10. In the third case the difference is 20. Thus, the smallest possible difference is 10.

1)
{4, 7, 4}
3
Returns: 3
2)
{4, 1, 2, 3}
3
Returns: 2
3)
{5, 4, 6, 1, 9, 4, 2, 7, 5, 6}
4
Returns: 1
4)
{47, 1000000000, 1, 74}
2
Returns: 27

Submissions are judged against all 116 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class WinterAndMandarins with a public method int getNumber(vector<int> bags, int K) · 116 test cases · 2 s / 256 MB per case

Submitting as anonymous