首页 › 题库 › C/C++编程考级 › C/C++编程三级 › 简答题
简答题 偏难
#7510

三足鼎立 当三个国家中的任何两国实力之和都大于第三国的时候,这三个国家互相结盟就呈“三足鼎立”之势,这种状态是最稳定的。 现已知本国的实力值,又给出 n 个其他…

三足鼎立

当三个国家中的任何两国实力之和都大于第三国的时候,这三个国家互相结盟就呈“三足鼎立”之势,这种状态是最稳定的。

现已知本国的实力值,又给出 n 个其他国家的实力值。我们需要从这 n 个国家中找 2 个结盟,以成三足鼎立。有多少种选择呢?

时间限制:10000

内存限制:65536

输入

输入首先在第一行给出 2 个正整数 n(2 ≤ n ≤ 105)和 P(≤ 109),分别为其他国家的个数、以及本国的实力值。随后一行给出 n 个正整数,表示n 个其他国家的实力值。每个数值不超过 109,数字间以空格分隔。

输出

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

样例输入

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}。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 C++ #include &lt;bits/stdc++.h&gt; using namespace std;   typedef long long ll;   const int N = 1e5 + 10;   int n, p; int a[N]; ll s;   int main() {     cin &gt;&gt; n &gt;&gt; p;     for (int i = 1; i &lt;= n; i ++)         cin &gt;&gt; a[i];          sort(a + 1, a + n + 1);       for (int i = 1; i &lt;= n; i ++) {         int l = i + 1, r = n;         int minn = abs(a[i]-p), maxx = a[i] + p;         int n1, n2; // 记录下标         if (l&gt;r) break;           while (l &lt;= r) { // 找到大于最小值的数             int mid = (l + r) / 2;             if (a[mid] &lt;= minn)                  l = mid + 1;             else                 r = mid - 1;         }         n1 = l;                  l = i + 1, r = n;         while (l &lt;= r) { // 找到小于最大值的数             int mid = (l + r) / 2;             if (a[mid] &lt; maxx)                 l = mid + 1;             else                 r = mid - 1;         }         n2 = r;           s += (n2 - n1) + 1;     }          cout &lt;&lt; s;     return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码2 C语言 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; long long n, x, cnt; int a[100005]; int cmpfunc(const void *a, const void *b) {     return (*(int *)a - *(int *)b); } int upper_bound(int arr[], int n, int x) {     int l = 0;     int r = n;     while (l &lt; r) {         int mid = l + (r - l) / 2;         if (arr[mid] &lt;= x) {             l = mid + 1;         } else {             r = mid;         }     }     return l; } int lower_bound(int arr[], int n, int x) {     int l = 0;     int r = n;     while (l &lt; r) {         int mid = l + (r - l) / 2;         if (arr[mid] &lt; x) {             l = mid + 1;         } else {             r = mid;         }     }     return l; } int main() {     scanf("%lld %lld", &amp;n, &amp;x);     for (int i = 0; i &lt; n; ++i) {         scanf("%d", &amp;a[i]);     }          qsort(a, n, sizeof(int), cmpfunc);          for (int i = 0; i &lt; n - 1; ++i) {         int l, r;         if (a[i] &lt; x) {             l = upper_bound(a + i + 1, n - i - 1, x - a[i]);         } else {             l = upper_bound(a + i + 1, n - i - 1, a[i] - x);         }         r = lower_bound(a + i + 1, n - i - 1, a[i] + x) - 1;                  if (l == n - i - 1) {             continue;         }                  cnt += (r - l + 1);     }          printf("%lld\n", cnt);     return 0; }</pre>
这道题暂未补解析。