USACO Current Problems Problem 'shelf' Analysis

by Neal Wu

Note that if it is possible to reach the bookshelf with a certain set of C cows, then it must be possible with the C tallest cows. Thus, in order to determine if it is possible to reach the bookshelf with C cows, we only have to check the C tallest cows. So we can loop over each C in increasing order, and find the first C that satisfies the conditions.

To do this, we must sort the numbers in non-increasing order beforehand in O(N log N) time, which can be done by either coding the sort yourself (using an efficient sort such as quicksort or mergesort) or by using the provided libraries. Afterward, we loop over all k from 1 to N, until we find the first k that produces a large enough sum. We must be careful to accumulate the sum with our loop efficiently to avoid having an O(N²) runtime.

With a properly-coded solution, the overall runtime will be O(N log N), as the majority of the runtime comes from the initial sort. The following is a sample solution:

#include <cstdio>
#include <algorithm>
using namespace std;

FILE *fout = fopen ("shelf.out", "w");
FILE *fin = fopen ("shelf.in", "r");

const int MAXN = 20005;

int N, B;
int heights [MAXN];

int solve ()
{
    int sum = 0;

// accumulate sum efficiently
    for (int i = 0; i < N; i++)
    {
        sum += heights [i];

        if (sum >= B)
            return i + 1;
    }

// should not happen
    return -1;
}

int main ()
{
    fscanf (fin, "%d %d", &N, &B);

    for (int i = 0; i < N; i++)
        fscanf (fin, "%d", heights + i);


// sort in non-increasing order
    sort (heights, heights + N);
    reverse (heights, heights + N);


    fprintf (fout, "%d\n", solve ());

    return 0;
}