Google Kickstart Round A 2019 - Training Problem: Training
  
  As the football coach at your local school, you have been tasked with
  picking a team of exactly P students to represent your school. There
  are N students for you to pick from. The i-th student has a skill
  rating Si, which is a positive integer indicating how skilled they
  are.
  
  You have decided that a team is fair if it has exactly P students on
  it and they all have the same skill rating. That way, everyone plays
  as a team. Initially, it might not be possible to pick a fair team, so
  you will give some of the students one-on-one coaching. It takes one
  hour of coaching to increase the skill rating of any student by 1.
  
  The competition season is starting very soon (in fact, the first match
  has already started!), so you'd like to find the minimum number of
  hours of coaching you need to give before you are able to pick a fair
  team.
  
  Input
  
  The first line of the input gives the number of test cases, T. T test
  cases follow. Each test case starts with a line containing the two
  integers N and P, the number of students and the number of students
  you need to pick, respectively. Then, another line follows containing
  N integers Si; the i-th of these is the skill of the i-th student.
  
  Output
  
  For each test case, output one line containing Case #x: y, where x is
  the test case number (starting from 1) and y is the minimum number of
  hours of coaching needed, before you can pick a fair team of P
  students.
  
  Limits
  
  
  Time limit: 15 seconds per test set.
  Memory limit: 1 GB.
  1 ≤ T ≤ 100.
  1 ≤ Si ≤ 10000, for all i.
  2 ≤ P ≤ N.
  Test set 1 (Visible)
  2 ≤ N ≤ 1000.
  Test set 2 (Hidden)
  2 ≤ N ≤ 105.
  
  
  Sample
  
  Input

3
4 3
3 1 9 100
6 2
5 5 1 2 3 4
5 5
7 7 1 7 7

  
  Output

Case #1: 14
Case #2: 0
Case #3: 6

  
  In Sample Case #1, you can spend a total of 6 hours training the first
  student and 8 hours training the second one. This gives the first,
  second and third students a skill level of 9. This is the minimum time
  you can spend, so the answer is 14.
  
  In Sample Case #2, you can already pick a fair team (the first and
  second student) without having to do any coaching, so the answer is 0.
  
  In Sample Case #3, P = N, so every student will be on your team. You
  have to spend 6 hours training the third student, so that they have a
  skill of 7, like everyone else. This is the minimum time you can
  spend, so the answer is 6.


My solution

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

void getData(int &amp;p, std::vector&lt;int&gt; &amp;skills) {
    int n;
    std::cin &gt;&gt; n &gt;&gt; p;
    skills.reserve(n);
    for (int i = 0; i &lt; n; i++) {
        int skill = 0;
        std::cin &gt;&gt; skill;
        skills.emplace_back(skill);
    }
}

int minTrainingTime(std::vector&lt;int&gt; &amp;skills, int p) {
    std::sort(skills.begin(), skills.end());
    int low = 0, high = p - 1;

    int currentResult = 0;
    for (int i = 0; i &lt; high; i++) {
        currentResult += skills[high] - skills[i];
    }

    int minResult = currentResult;
    int remainingPossibilities = skills.size() - p;
    for (int i = 0; i &lt; remainingPossibilities; i++) {
        currentResult -= skills[++high] - skills[low++];
        currentResult += p * (skills[high] - skills[high - 1]);
        minResult = std::min(minResult, currentResult);
    }

    return minResult;
}

int main() {
    int t = 0;
    std::cin &gt;&gt; t;
    for (int testCase = 0; testCase &lt; t; testCase++) {
        int p;
        std::vector&lt;int&gt; skills;
        getData(p, skills);

        std::cout &lt;&lt; "Case #" &lt;&lt; testCase + 1 &lt;&lt; ": " &lt;&lt; minTrainingTime(skills, p) &lt;&lt; std::endl;
    }
}


Analysis

Time complexity: \$O(n\log n)\$, dominated by sorting

Space complexity: \$O(1)\$, not counting the original data given by the problem
First of all, this looks good to me! I have some minor comments.

General comments


Consider compiling with -Wconversion. It will give you a couple of hints where you implicitly convert between std::vector::size_type (usually std::size_t) and int. Whether you work with unsigned data types for skills and quantities might be a matter of taste, but I think you should be aware of the conversion issue. Also, this compiler flags gives you (on my machine)


  implicit conversion loses integer precision: unsigned long to int [-Wshorten-64-to-32]

int remainingPossibilities = skills.size() - p;



which should definitely worth tackling even if the problem description specifies input characteristics that make a digit loss impossible.
Not that this will be an issue for this example, but when you want to be as fast as possible, don't use &lt;iostream&gt;, but &lt;cstdio&gt; instead.


Input handling/parameter types


When retrieving the input data, don't pass non-const references, but prefer returning by value instead. (N)RVO will make sure there is no overhead. As you have more than one value, define a small, custom type for this. So, I'd suggest going with

struct TestCaseInput {
   int nToChoose;
   std::vector&lt;int&gt; skills;
};

TestCaseInput getData();
int minTrainingTime(TestCaseInput&amp; input);


cf. the Core Guidelines on this topic, F.20 and F.21
std::vector::emplace_back makes sense when you can in-place construct an object with given parameters, but when you pass the already existing object to this function, it's probably clearer to use push_back. In the case of an integral value, it doesn't matter anyhow whether you move-construct or copy it. As an alternative, you could also

std::vector&lt;int&gt; skills(n); // Allocates and set all values to zero

for (int i = 0; i &lt; n; i++)
    std::cin &gt;&gt; skills[i]; // No temporary variable required


And also have a look at the combination of std::copy_n and std::istream_iterator that @papagaga suggests to eliminate the manual loop here.


Main function minTrainingTime


In the first loop, you read skills[high] in every iteration, even though this value doesn't change. Instead, just read it once and save it in a variable. Or, leave it as it is and verify that the compiler optimizes this away anyway.
You can also replace this whole first loop by including &lt;numeric&gt; and using std::accumulate with an initial value high*skills[high] and std::minus&lt;&gt;{} as the binary operation parameter.
If you can const-qualify a variable, do so:

const int remainingPossibilities = skills.size() - p;

But if can alternative reduce the scope of such a variable and by that even eliminate another one (the loop counter i), do so instead (as long as the negative influence on the readability is not too big, which I think is ok here):

// remainingPossibilities is now superfluous, just use the for loop for
// the initialization and count differently:
for (int n = skills.size() - p; n != 0; n--) { /* ... */ }

You might want to consider an additional level of indirection for the function minTrainingTime here, as it can equally well operate on random access iterators instead of indices. This way, you eliminate the dependency of this function on the actual value type that you are using (which also considerably reduces the number of -Wconversion warnings at one go), as well as the dependency on the container type. Using some of the above hints, the resulting function template looks e.g. like this:

template &lt;class RandomAccesIt, class T&gt;
auto minTrainingTime(RandomAccesIt first, RandomAccesIt last, T p)
{
    using value_type = typename RandomAccesIt::value_type;
    auto low = first, high = std::next(first, p - 1);
    const value_type init = std::distance(low, high)*(*high);

    value_type currentResult = std::accumulate(first, high, init, std::minus&lt;&gt;{});
    value_type minResult = currentResult;

    for (auto n = std::distance(first, std::prev(last, p)); n != 0; --n) {
        currentResult -= *++high - *low++;
        currentResult += p*(*high - *std::prev(high));
        minResult = std::min(minResult, currentResult);
    }

    return minResult;
}


and can be deduced and invoked by minTrainingTime(skills.begin(), skills.end(), p).