深圳游戏网站开发,淮安设计网站,新品发布会ppt参考,大宗交易平台当三个国家中的任何两国实力之和都大于第三国的时候#xff0c;这三个国家互相结盟就呈“三足鼎立”之势#xff0c;这种状态是最稳定的。
现已知本国的实力值#xff0c;又给出 n 个其他国家的实力值。我们需要从这 n 个国家中找 2 个结盟#xff0c;以成三足鼎立。有多少…当三个国家中的任何两国实力之和都大于第三国的时候这三个国家互相结盟就呈“三足鼎立”之势这种状态是最稳定的。
现已知本国的实力值又给出 n 个其他国家的实力值。我们需要从这 n 个国家中找 2 个结盟以成三足鼎立。有多少种选择呢
输入格式 输入首先在第一行给出 2 个正整数 n2≤n≤105和 P≤10e9分别为其他国家的个数、以及本国的实力值。随后一行给出 n 个正整数表示n 个其他国家的实力值。每个数值不超过 10e9数字间以空格分隔。
输出格式 在一行中输出本国结盟选择的个数。
输入样例 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}。
知识引入 AC本道题需要用到C STL中的lower_bound()和upper_bound函数。 lower_bound(type a[ ], type* p1, type* p2) 能够查找第一个大于等于当前数字的地址
upper_bound(type a[ ], type* p1, type* p2) 能够查找第一个大于没有等于当前数字的地址
思路 根据题目定义可知任意两个国家的实力值要大于第三个。如果直接双循环搜索必然超时不过用来骗分不错 让我们想想假如把各个国家的实力值进行排序依次遍历数组如果要满足当前的实力值和题目给定的实力值三足鼎立那么第三个国家的实力值的范围可以确定下来的。 我们不妨这样想设当前实力值加上输入给定的实力值为temp1当前实力值减去输入给定的实力值的绝对值为temp2在当前位置后找第一个大于等于temp的数和第一个大于temp2的数。当前遍历的国家可以和两个位置数之间的国家形成联盟每次遍历总数加上两数之差最后输出总是即可。
参考代码
#includebits/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(num1, numn1);int k, q;for(int i 1; i n; i){q lower_bound(numi1, numn1, pnum[i]) - (num1);k upper_bound(numi1, numn1, abs(num[i]-p)) - (num1);sum q-k;}printf(%ld\n, sum);return 0;
}
