题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5101
题目意思：给出 n 个 classes 和 Dudu 的 IQ（为k），每个classes 都有相应的人，每个人又有相应的IQ。现在要求从这些classes挑选两个人，满足IQ之和 > k，不过要满足这两个人不能来自同一个class的。
解题思路不难想出，直接所有人两两之和 > k - 同一个class 两两之和 > k 就是答案了。
不过很容易超时！！！！
用二分就可以过了。二分有两个STL函数：lower_bound 和 upper_bound。这里用到lower_bound，它一般是跟vector一起用的。看了好久终于看懂了= =，十分强大～～～呀！如果大家对这两个函数比较熟悉，可以直接略过以下注释内容（只结合自己的理解说一下lower_bound，可能有误导他人成分，希望大家多多包涵）。共同的一点就是都需要对操作数组进行排序。
/********************************************************
假设有vector<int> q，第三个参数假设用key来表示。
lower_bound(q.begin(), q.end(), key) 这个东西并不是返回一个int数值，而是vector<int>::iterator vit，假设vit = lower_bound(q.begin(), q.end(), key)（这样为了方便解说）。但是如果 vit - q.begin()，返回的是 >= key 且从左到右开始数起的第一个元素下标（int 数值），其实就是插入key的位置，如果这个数组中有和key相等的数，就插入跳过所有和key相同的数的下一位置（结合下面例子中的key = 10来看）。如果 q.end() - vit 返回的是 >= key 且从右数起的第一个元素的下标（i），但满足下标i-1 这个数是 < key的。至于 *vit 就是具体指向的数值啦，不是下标！
例如有 4，10，10，30，69，70，96，100（第一个元素下标从0开始）
vit - q.begin() q.end() - vit
key = 9， 1 7
key = 10 3（不是1，注意） 5
*****************************************/
接着结合思路来讲，先给出一组数据：
1
3 3
3 5 2 7
2 1 9
3 4 2 6
我们声明一个vector<int> p[maxn]，p[0] 压入所有人的IQ ,p[i]压入对应第 i 个班里所有人的IQ，然后对p[0]～p[n] 从小到大排序(有n个class，但还有一个包含所有class的p[0])。
处理完之后 p[0]： 1 2 2 4 5 6 7 9
p[1]： 2 5 7
p[2]: 1 9
p[3]: 2 4 6
然后遍历每个class的人，假如从p[1] 的 2（用v来表示） 开刀。
LL num1 = p[0].end() - lower_bound(p[0].begin(), p[0].end(), k-v+1);
表示 >= k-v+1 从右开始数 >= （3-2+1） 的数的下标，但前一个数必须要 < 2，那么就是p[0]中数组下标为1，表示 2 这个数，跟 2，4，5，6，7，9 这些数相加可以 > k。p[1]同理。之后要相减保存到ans中。但ans 最终要除以2才是答案（这个...我也纠结了好久）
举个例子就明白了。
例如处理到6，那么 k-v+1变成负数了，返回的是数组下标 0，就是表示 6 跟其他所有数两两相加都满足 > k，有1+6，2+6，....6+7，6+9；处理到7的时候，也是返回数组下标0，于是有1+7, 2+7,...,6+7, 7+9。 6+7被选了两次！！！！所以要除以2！
最后一点就是记得将vector清空啦～～～～
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std; #define pb push_back
typedef __int64 LL;
const int maxn = + ;
vector<int> p[maxn]; int main()
{
int T, n, k, m, input;
while (scanf("%d", &T) != EOF)
{
while (T--)
{
p[].clear();
scanf("%d%d", &n, &k);
for (int i = ; i <= n; i++)
{
scanf("%d", &m);
p[i].clear();
for (int j = ; j < m; j++)
{
scanf("%d", &input);
p[i].pb(input);
p[].pb(input);
}
sort(p[i].begin(), p[i].end());
}
sort(p[].begin(), p[].end()); LL ans = ;
for (int i = ; i <= n; i++)
{
for (int j = ; j < p[i].size(); j++)
{
int v = p[i][j];
LL num1 = p[].end() - lower_bound(p[].begin(), p[].end(), k-v+);
LL num2 = p[i].end() - lower_bound(p[i].begin(), p[i].end(), k-v+);
ans += num1 - num2;
}
}
printf("%I64d\n", ans >> );
}
}
return ;
}