HDU 5101 Select（BestCoder Round #17）

Problem Description：

One day, Dudu, the most clever boy, heard of ACM/ICPC, which is a very interesting game. He wants to take part in the game. But as we all know, you can't get good result without teammates.
So, he needs to select two classmates as his teammates. 
In this game, the IQ is very important, if you have low IQ you will WanTuo. Dudu's IQ is a given number k. We use an integer v[i] to represent the IQ of the ith classmate. 
The sum of new two teammates' IQ must more than Dudu's IQ.
For some reason, Dudu don't want the two teammates comes from the same class.
Now, give you the status of classes, can you tell Dudu how many ways there are.

 

Input：

There is a number T shows there are T test cases below. (T≤20)
For each test case , the first line contains two integers, n and k, which means the number of class and the IQ of Dudu. n ( 0≤n≤1000 ), k( 0≤k<231 ).
Then, there are n classes below, for each class, the first line contains an integer m, which means the number of the classmates in this class, and for next m lines, each line contains an integer v[i], which means there is a person whose iq is v[i] in this class. m( 0≤m≤100 ), v[i]( 0≤v[i]<231 )

 

Output：

For each test case, output a single integer.

 

Sample Input：

1

3 1

1 2

1 2

2 1 1

 

Sample Output：

5

 

题意：一个很聪明的ACMer，现在他需要两个队友（这两个队友的智商之和必须大于他的智商，且这两个人不在同一个班）去参加ICPC，现在给出的他的智商k，和班级的个数n，每个班级的人数m，以及每个人中每个人的智商a[i]，求出他可以做出的选择数。

 

分析：我们知道将所有人统计在一个数组b中，然后排序后二分查找可以和b[i]一起组队的人数，所有的加起来就是所有的选择数ans2，但是这里面包含了同班同学，所以我们要找到每个人在每个班中组队的个数ans1，那么最终能够达到这个人要求的个数为ans2-ans1。

 

这里用到新的二分查找（都是在排序之后的查找）：lower_bound（a，a+n，x）- a，它的含义是从数组a中（下标从0~n-1）查找大于等于x的第一个数的位置，如果x在数组a中，那么返回第一个x的位置，如果a中不存在x，返回x可以插入的位置（插入之后排序不变）；

upper_bound（a，a+n，x）- a，它的含义是从数组a中（下标从0~n-1）查找大于等于x的最后一个数的位置，如果x在数组a中，那么返回最后一个x的位置，如果a中不存在x，返回x可以插入的位置（插入之后排序不变）。

#include<stdio.h>
#include<string.h>
#include<queue>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;

const int N=1e6+10;
const int INF=0x3f3f3f3f;
const int MOD=1e9+7;

typedef long long LL;

LL a[110], b[N];

int main ()
{
    int T, n, m, i, j, num, idex;
    LL k, ans1, ans2;

    scanf("%d", &T);

    while (T--)
    {
        num = ans1 = ans2 = 0;

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

        for (i = 0; i < n; i++)
        {
            scanf("%d", &m);

            for (j = 0; j < m; j++)
            {
                scanf("%lld", &a[j]);
                b[num++] = a[j];
            }

            sort(a, a+m);

            for (j = 0; j < m; j++)
            {
                idex = upper_bound(a+j, a+m, k-a[j])-a; ///大于k-a[j]就可以与a[j]组队了
                ans1 += m-idex+1; ///计算每个班里的人可以与之组队的人数
            }
        }

        sort(b, b+num);

        for (i = 0; i < num; i++)
        {
            idex = upper_bound(b+i, b+num, k-b[i])-b;
            ans2 += num-idex+1; ///计算每个人可以与之组队的人数
        }

        printf("%lld
", ans2-ans1);
    }

    return 0;
}