Vaccination Problem
The world health organization wants to establish a total of
B vaccination clinics across N cities to immunization people against fatal
diseases. Every city must have at least 1 clinic, and a clinic can only
vaccinate people in the same city where they live. The goal is to minimize the
number of vaccination kits needed in the largest clinic. For example suppose
you have.
1.
2 cities and
2.
7 clinics to be opened
3.
200.000 is the population of first city
4.
50,000 is the population of second city
5.
Two clinics can open in the first city and
6.
Five in the second. This way
7.
100,000 people can be immunized in each of the
two clinics in first city, and
8.
100.000 people can be immunized in the each
clinic in the second city
9.
So the maximum number of people to be immunized
in the largest clinic is 10,000
Input:
Two integers in the first line, N, the number of cities, and
B, the total number of clinics to be opened
Each of the following N lines contains an integer ai, the
population of city i
Output:
One integer representing the maximum number of people to be
immunized in any single clinic
Constraints:
1<=N<=500,000
N<=B<=2,000,000
1<=ai<=5,000,000
Sample input:
2 7
200000
500000
Sample output:
100000
Solution (In C) using qsort
==================================================================
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct city {
long long population;
long long num_of_clinics;
long long load; /* population assigned per clinic */
} city;
int cmp_cities(const void * city1, const void *city2)
{
city *mycity1 , *mycity2;
mycity1 = (city *) city1;
mycity2 = (city *) city2;
return (mycity1->load - mycity2->load);
}
int main()
{
long long i;
city cities[1024];
long long num_of_cities, num_of_clinics;
scanf("%lld %lld",&num_of_cities,
&num_of_clinics);
for(i = 0;i < num_of_cities; i++)
{
scanf("%lld",
&cities[i].population);
/* assign one clinic per city */
/* assign one clinic per city */
cities[i].num_of_clinics = 1;
/* Initial load per clinic is total population of city */
cities[i].load = cities[i].population;
}
/* sort on the basis of load per clinic in increasing order*/
qsort(cities, num_of_cities, sizeof(city),cmp_cities);
/* assign one remaining clinic to the city
* having highest load (array is sorted in increasing
* order) in each iteration to reduce the max load
*/
for (i = 0; i < (num_of_clinics - num_of_cities);
i++)
{
cities[num_of_cities -1].num_of_clinics ++;
cities[num_of_cities -1].load = cities[num_of_cities -1].population/cities[num_of_cities -1].num_of_clinics;
/* population=1001 and clinics=2 then load=501 */
if (cities[num_of_cities -1].population%cities[num_of_cities
-1].num_of_clinics)
cities[num_of_cities
-1].load++;
/* Keep the array sorted in increasing order of load */
qsort(cities, num_of_cities,
sizeof(city),cmp_cities);
}
/* Dump the clinic having highest load */
printf("%lld\n",cities[num_of_cities
-1].load);
return 0;
}
==================================================================
Sample input 1:
3 7
2
42
48
2
42
48
Output:
16
Sample input 2:
3 7
2
42
49
2
42
49
Output:
17
==================================================================
#include <iostream>
#include <queue>
using namespace std;
struct city {
long long population;
long long num_of_clinics;
long long load; /* population assigned per clinic */
};
class cmp_cities {
public:
bool operator () (city &city1, city &city2) // Returns true if t1 is earlier than t2
{
if (city1.load < city2.load) return true;
return false;
}
};
int main()
{
long long i;
city tmp_city;
long long num_of_cities, num_of_clinics;
priority_queue <city, vector<city>, cmp_cities> pq;
cin >> num_of_cities >> num_of_clinics;
for(i = 0;i < num_of_cities; i++)
{
cin >> tmp_city.population;
/* assign one clinic per city */
tmp_city.num_of_clinics = 1;
/* Initial load per clinic is total population of city */
tmp_city.load = tmp_city.population;
pq.push(tmp_city);
}
/* assign one remaining clinic to the city
* having highest load (priority_queue is sorted in increasing
* order) in each iteration to reduce the max load
*/
for (i = 0; i < (num_of_clinics - num_of_cities); i++)
{
tmp_city = pq.top();
tmp_city.num_of_clinics ++;
tmp_city.load = tmp_city.population/tmp_city.num_of_clinics;
/* population=1001 and clinics=2 then load=501 */
if (tmp_city.population%tmp_city.num_of_clinics)
tmp_city.load++;
pq.pop();
/* priority_queue remains sorted in increasing order of load */
pq.push(tmp_city);
}
/* Dump the clinic having highest load */
tmp_city = pq.top();
cout << tmp_city.load;
return 0;
}
==================================================================
==================================================================
Solution (In C++) using priority_queue
==================================================================#include <iostream>
#include <queue>
using namespace std;
struct city {
long long population;
long long num_of_clinics;
long long load; /* population assigned per clinic */
};
class cmp_cities {
public:
bool operator () (city &city1, city &city2) // Returns true if t1 is earlier than t2
{
if (city1.load < city2.load) return true;
return false;
}
};
int main()
{
long long i;
city tmp_city;
long long num_of_cities, num_of_clinics;
priority_queue <city, vector<city>, cmp_cities> pq;
cin >> num_of_cities >> num_of_clinics;
for(i = 0;i < num_of_cities; i++)
{
cin >> tmp_city.population;
/* assign one clinic per city */
tmp_city.num_of_clinics = 1;
/* Initial load per clinic is total population of city */
tmp_city.load = tmp_city.population;
pq.push(tmp_city);
}
/* assign one remaining clinic to the city
* having highest load (priority_queue is sorted in increasing
* order) in each iteration to reduce the max load
*/
for (i = 0; i < (num_of_clinics - num_of_cities); i++)
{
tmp_city = pq.top();
tmp_city.num_of_clinics ++;
tmp_city.load = tmp_city.population/tmp_city.num_of_clinics;
/* population=1001 and clinics=2 then load=501 */
if (tmp_city.population%tmp_city.num_of_clinics)
tmp_city.load++;
pq.pop();
/* priority_queue remains sorted in increasing order of load */
pq.push(tmp_city);
}
/* Dump the clinic having highest load */
tmp_city = pq.top();
cout << tmp_city.load;
return 0;
}
