當(dāng)三個(gè)國家中的任何兩國實(shí)力之和都大于第三國的時(shí)候，這三個(gè)國家互相結(jié)盟就呈“三足鼎立”之勢，這種狀態(tài)是最穩(wěn)定的。

現(xiàn)已知本國的實(shí)力值，又給出 n 個(gè)其他國家的實(shí)力值。我們需要從這 n 個(gè)國家中找 2 個(gè)結(jié)盟，以成三足鼎立。有多少種選擇呢？

輸入格式：
輸入首先在第一行給出 2 個(gè)正整數(shù) n（2≤n≤10?5）和 P（≤10e?9），分別為其他國家的個(gè)數(shù)、以及本國的實(shí)力值。隨后一行給出 n 個(gè)正整數(shù)，表示n 個(gè)其他國家的實(shí)力值。每個(gè)數(shù)值不超過 10e?9，數(shù)字間以空格分隔。

輸出格式：
在一行中輸出本國結(jié)盟選擇的個(gè)數(shù)。

輸入樣例：
7 30
42 16 2 51 92 27 35

輸出樣例：
9

樣例解釋：
能聯(lián)合的另外 2 個(gè)國家的 9 種選擇分別為：

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

知識(shí)引入
AC本道題需要用到C++ STL中的lower_bound()和upper_bound（）函數(shù)。
lower_bound(type a[ ], type* p1, type* p2)
能夠查找第一個(gè)大于等于當(dāng)前數(shù)字的地址

upper_bound(type a[ ], type* p1, type* p2)
能夠查找第一個(gè)大于（沒有等于）當(dāng)前數(shù)字的地址

思路
根據(jù)題目定義可知任意兩個(gè)國家的實(shí)力值要大于第三個(gè)。如果直接雙循環(huán)搜索，必然超時(shí)（不過用來騙分不錯(cuò)）
讓我們想想，假如把各個(gè)國家的實(shí)力值進(jìn)行排序，依次遍歷數(shù)組，如果要滿足當(dāng)前的實(shí)力值和題目給定的實(shí)力值三足鼎立，那么第三個(gè)國家的實(shí)力值的范圍可以確定下來的。
我們不妨這樣想，設(shè)當(dāng)前實(shí)力值加上輸入給定的實(shí)力值為temp1，當(dāng)前實(shí)力值減去輸入給定的實(shí)力值的絕對(duì)值為temp2，在當(dāng)前位置后找第一個(gè)大于等于temp的數(shù)和第一個(gè)大于temp2的數(shù)。當(dāng)前遍歷的國家可以和兩個(gè)位置數(shù)之間的國家形成聯(lián)盟，每次遍歷總數(shù)加上兩數(shù)之差，最后輸出總是即可。

參考代碼

#include<bits/stdc++.h> using namespace std; typedef long long ll; int num[100005];int main() {int n, p;scanf("%d %d", &n, &p);ll sum = 0;for(int i = 1; i <= n; i++)scanf("%d", &num[i]);sort(num+1, num+n+1);int k, q;for(int i = 1; i <= n; i++){q = lower_bound(num+i+1, num+n+1, p+num[i]) - (num+1);k = upper_bound(num+i+1, num+n+1, abs(num[i]-p)) - (num+1);sum += q-k;}printf("%ld\n", sum);return 0; }

總結(jié)

以上是生活随笔為你收集整理的PTA 三足鼎立 (lower_bound()+upper_bound())的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。