Medical Centers :
Difficulty Level : Easy
Submissions : 596
Asked In :
Marks :100
: 10 | : 1
The Health Ministry of Torris county has decided to set up medical centres for the benefit of its citizens. The Ministry selects N different cities in the county in which to establish a medical centre.
Each city is identified by a city ID ranging from 0 to N 1. Multiple medical centres are needed in different cities according to requirements. Each day a medical centre will be set up in one of the selected cities. On any two consecutive days, the chosen city must be different.
Write an algorithm to determine the maximum number of medical centres that will be set up in the county covering the maximum number of locations.
The first line of the input consists of an integer - numCity representing the number of cities selected for a medical centre (N).($$$1 \le N \le 10^4$$$) The next line consists of N space-separated integers - loc*1*, loc*2*,.. loc*N* representing the number of locations to set up a medical center in a city ($$$1 \le loc[i] \le 10^5$$$).
Print an integer representing the maximum number of medical centres that will be set up in the county covering the maximum number of locations.
3 11 5 4
19
In reference to test case 1 :
The first, second and third cities are selected with locations 11, 4 and 5, respectively.
The locations of different cities are selected on successive days in a sequence:
1st, 2nd, 1st, 3rd, 1st, 2nd, 1st, 3rd,1st, 2nd, 1st, 3rd, 1st, 2nd, 1st, 3rd, 1st, 3rd, 1st
So, the maximum number of medical centres that may be set up in the county is 19
