Costume Party [Neal Wu, 2007]


It's Halloween! Farmer John is taking the cows to a costume party, but unfortunately he only has one costume. The costume fits precisely two cows with a length of S (1 <= S <= 1,000,000). FJ has N cows (2 <= N <= 20,000) conveniently numbered 1...N; cow i has length Li (1 <= Li <= 1,000,000). Two cows can fit into the costume if the sum of their lengths is no greater than the length of the costume. FJ wants to know how many pairs of two distinct cows will fit into the costume.
Дадени са n естествени числа. Да се намери броя на двойките числа, чиято сума не надвишава предварително зададено число.

Домашно: Да се използва функция от STL за двоичното търсене и да се сравни ефективността на двете реализации.


INPUT FORMAT:
* Line 1: Two space-separated integers: N and S

* Lines 2..N+1: Line i+1 contains a single integer: Li

SAMPLE INPUT (file costume.in):
4 6
3
5
2
1

OUTPUT FORMAT:
* Line 1: A single integer representing the number of pairs of cows FJ
        can choose. Note that the order of the two cows does not
        matter.

SAMPLE OUTPUT (file costume.out):
4

OUTPUT DETAILS:
The four pairs are as follows: cow 1 and cow 3; cow 1 and cow 4; cow 2 and cow 4; and finally cow 3 and cow 4.

We first sort the heights, using an efficient sort, which takes O(N log N) time. Then, for each height k in the list, we wish to (efficiently) find the index of the largest height that, when added to k, produces a sum less than H. After we find this index, we can count the number of heights that, when added to k, satisfy the given property. The simplest way to find this is with a binary search, which is implemented in the solution below:

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

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

const int MAXN = 20005;
int N, H, total;
int height [MAXN];

// finds the index of the first position whose height is <= value
inline int binsearch (int value)
{
    int lo = 0, hi = N - 1, mid;
    while (lo < hi)
    {
        mid = (lo + hi + 1) >> 1;
        if (height [mid] <= value) lo = mid;
        else hi = mid - 1;
    }
    return lo;
}

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

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

    sort (height, height + N);

    total = 0;
    for (int i = 0; i < N; i++)
    {
    // query the largest index satisfying the conditions
        int ind = binsearch (H - height [i]);

    // only count if ind > i
        if (ind > i) total += ind - i;
        else break;
    }
    fprintf (fout, "%d\n", total);
    return 0;
}