PTA 7-5 三足鼎立（25分）

当三个国家中的任何两国实力之和都大于第三国的时候，这三个国家互相结盟就呈“三足鼎立”之势，这种状态是最稳定的。
现已知本国的实力值，又给出 n 个其他国家的实力值。我们需要从这 n 个国家中找 2 个结盟，以成三足鼎立。有多少种选择呢？

输入格式

输出格式

在一行中输出本国结盟选择的个数。

输入样例

7 30
42 16 2 51 92 27 35

输出样例

9

样例解释

能联合的另外 2 个国家的 9 种选择分别为：

{16, 27}, {16, 35}, {16, 42}, {27, 35}, {27, 42}, {27, 51}, {35, 42}, {35, 51}, {42, 51}。

限制条件

C++代码

#include <iostream>using namespace std;void subheap(int a[], int i, int n) //比较父结点和子结点，在子树中生成最大堆
{int parent = i;int child = 2 * i + 1; //堆从0开始，父结点为i，则左孩子为2i+1while(child < n){if(child + 1 < n && a[child] < a[child + 1]) //如果这个父结点有右孩子，并且右孩子比左孩子大{child += 1; //child的值是左右孩子中较大孩子的位置}if(a[child] > a[parent]) //如果孩子结点比父结点大，交换二者{int tem = a[child];a[child] = a[parent];a[parent] = tem;parent = child;}child = child * 2 + 1; //由上至下做比较}
}void trip(int a[], int num) //第一趟堆排序，将最大值放到根结点的位置 //num为数组元素个数
{for(int i = num / 2 - 1; i >= 0; i--) // n/2+1是倒数第二排最后一个位置，也就是右下角那棵子树的根结点{subheap(a, i, num);}
}void heapsort(int a[], int num) //堆排序
{trip(a, num);for(int i = num - 1; i > 0; i--){int f = a[0];a[0] = a[i];a[i] = f; //交换根结点和最后一个元素的位置subheap(a, 0, i);}}/* 这个排序会有四个测试点显示超时
int trip(int a[], int left, int right) //一趟快速排序
{int pivot = a[left];while(left < right){while(left < right && a[right] >= pivot) //left和right一直在变{right--;}a[left] = a[right];while(left < right && a[left] <= pivot){left++;}a[right] = a[left];}a[left] = pivot; //此时left=rightreturn left; //返回这一趟pivot的位置
}void quicksort(int a[], int left, int right) //快速排序
{if(left < right){int piv = trip(a, left, right);quicksort(a, left, piv - 1);quicksort(a, piv + 1, right);}
}
*/long binarysearch(int a[], int left, int right, int p) //二分查找
{int num = right;long cnt = 0;for(int i = 0; i < num; i++){int sum = a[i] + p; //和int dif; //差if(a[i] - p > 0){dif = a[i] - p;}else{dif = p - a[i];}left = i + 1;right = num;while(left <= right) //这里要有等号{int mid = (left + right) / 2;if(a[mid] >= sum){right = mid - 1;}else //没有else，left<=right一直成立，死循环{left = mid + 1;}}int high = right;left = i + 1;right = num;while(left <= right){int mid = (left + right) / 2;if(a[mid] <= dif){left = mid + 1;}else{right = mid - 1;}}int low = left;int tem = high - low + 1;cnt += tem;}return cnt;
}int main()
{int n, p;cin >> n >> p; //其他国家的个数n 本国的实力值pint sv[n]; //n个国家的实力值for(int i = 0; i < n; i++){int a;cin >> a;sv[i] = a;}heapsort(sv, n);//quicksort(sv, 0, n - 1); //数组索引从0开始//sort(sv, sv + n); //sort不超时/* 暴力破解会超时int cnt = 0; //记录符合条件的组合数量for(int i = 0; i < n - 1; i++){int sum = sv[i] + p;int dif;if(sv[i] - p > 0){dif = sv[i] - p;}else{dif = p - sv[i];}for(int j = i + 1; j < n; j++){if(sv[j] < sum && sv[j] > dif){cnt++;}}}cout << cnt;
*/cout << binarysearch(sv, 0, n - 1, p);return 0;
}

运行结果