Program in C/C++ for Vaccination Problem

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 */

    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 

Output:

16

Sample input 2:

3 7
2
42
49

Output:

17
==================================================================

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;
}

==================================================================