MilkConsumption
SRM 765 · 2019-08-22 · by misof
Problem Statement
For a presentation you are comparing the amounts of milk drank by people in various countries.
The countries are numbered 0 through N-1, for some N.
The data you have are two
Among all non-empty subsets of these countries, you are looking for the one for which the consumption per capita (i.e., the average amount of milk consumed by one person) is maximal.
Find any one such subset of countries and return a
Notes
- There may be more than one correct answer. Each optimal answer will be accepted.
- The country numbers in the int[] you return must be distinct, but they may be in any order.
Constraints
- population will contain between 1 and 50 elements, inclusive.
- totalConsumption will contain the same number of elements as population.
- Each element of population will be between 1 and 20,000,000, inclusive.
- Each element of totalConsumption will be between 1 and 20,000,000, inclusive.
{10, 10, 10, 10}
{47, 47, 47, 47}
Returns: {2, 3, 0 }
All countries have the same population and all countries drank the same amount of milk. In this situation any non-empty subset of countries is a valid answer.
{1234567, 2345678, 3456789, 4567890}
{2345678, 3456789, 4567890, 5678901}
Returns: {0 }
{98, 120, 40, 135, 40}
{4606, 5167, 1880, 1351, 1879}
Returns: {0, 2 }
Together, countries 0 and 2 have 98 + 40 = 138 people and they drank a total of 4606 + 1880 = 6486 litres of milk. Thus, this subset of countries has consumed (6486 / 138) litres of milk per capita. No other subset of countries has consumed more milk per person, so this is one of the optimal answers.
{1}
{20000000}
Returns: {0 }
{20000000}
{1}
Returns: {0 }
Submissions are judged against all 94 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class MilkConsumption with a public method vector<int> findMaxRegion(vector<int> population, vector<int> totalConsumption) · 94 test cases · 2 s / 256 MB per case