10030. SpaceX

 

Elon Musk plans to send his spaceships to k different planets. To do this, he has n spaceships. Initially, it is known where each ship will be sent. The planets are numbered from 1 to 109 . As SpaceX’s chief space engineer, you are entitled to change the destination of any ship. For the minimum number of changes you need to make sure that all ships are sent to k different planets.

 

Input. The first line contains two numbers n (1 ≤ n ≤ 105) and k (1 ≤ k ≤ n). Second line contains n integers pi (1 ≤ pi ≤ 105) – the original ship destinations.

 

Output. Print the minimum number of changes.

 

Sample input 1

Sample output 1

3 1

1 5 3

2

 

 

 

Sample input 2

Sample output 2

5 4

10 1 2 1 10

1

 

 

 

SOLUTION

map data structures

 

Algorithm analysis

For each destination p in the map m, count the number of ships m[p] sent there. For example, in the second test, two ships are sent to planet 1, one ship is sent to planet 2, and two ships are sent to planet 10. The map structure looks like this:

 

The size of the map is m.size () = 3, all ships are sent to 3 planets. The ships should be sent to exactly k = 4 different planets. If m.size () < k, then k – m.size() ships should change the course.

Consider the case where spaceships are sent to more than k planets. Let k = 4, but the map structure will be as follows:

 

17 ships were sent to 6 planets. From the two planets, ships should be redirected to any of the 4 remaining ones. Since you want to minimize the number of changes, you should find the two planets to which the least number of ships are sent. Sort the numbers – the number of ships sent to the planets. And find the sum of the two smallest ones.

 

Algorithm realization

Declare the data structures.

 

map<long long, long long> m;

vector<long long> v;

 

Read the input data.

 

scanf("%d %d", &n, &k);

for (i = 0; i < n; i++)

{

  scanf("%d", &x);

 

In m[x] count the number of ships sent to planet x.

 

  m[x]++;

}

 

If all spaceships are sent to less than k planets, then the minimum number of changes is k – m.size().

 

if (m.size() < k)

{

  printf("%d\n", k - m.size());

  return 0;

}

 

Spaceships are sent to more than k planets. Construct a vector v that contains the number of ships sent to different planets.

 

for (iter = m.begin(); iter != m.end(); iter++)

  v.push_back((*iter).second);

 

Sort the vector v.

 

sort(v.begin(), v.end());

 

Look for the sum of m.size() – k smallest numbers (from this number of planets the ships destinations should be changed).

 

sum = 0;

for (i = 0; i < m.size() - k; i++)

  sum += v[i];

 

Print the answer.

 

printf("%lld\n", sum);