点击打开链接
孙云球 Description 大家一起来玩孙云球吧。 众所周知，孙云球是一种好玩有炫酷的球类游戏，由编程始祖 SLF 发明。但是评价一个 球队的战力是的特殊的，给定 n 个人，每个人的身高是 a[i]，每有一个三个人的组合 （x，y，z）满足以下条件即可提供 1 的战斗力。条件如下： 1. a[x] < a[y] < a[z] 2. a[y] – a[x] ≤ a[z] – a[y] ≤ 2 * （a[y] – a[x]） SLF 同志的号召能力非常强大，组建的队伍身高千奇百怪，有 1cm 的也有 100km 的。但是， 他迫切期待他组建的这支球队的战力，你能告诉他吗？ Input 第一行一个数 n，表示球队的人数。 接下来 n 行每行一个数，a[i]表示每个人的身高（1 ≤ a[i]≤ 10^9） Output 一行一个数，表示 SLF 战队的战斗力。 Sample Input 5 3 1 10 7 4 Sample Output 4 Hint 样例解释：1-3-7, 1-4-7, 4-7-10, and 1-4-10 对于 100%的数据，1 ≤ n ≤ 1000 思路 直接枚举算了一下是1e9数量级的，肯定会超时 结果交上去试了一下竟然过了（760ms）,可见数据比较水 考虑二分进行优化 利用c++ stl中的函数lower_bound ： ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)返回一个非递减序列[first, last)中的第一个大于等于值val的位置。 注：调用lower_bound之前必须确定序列为有序序列，这也是二分的基础 另外要注意下标的边界情况，有效的范围是0~n-1 代码示例 #include<bits/stdc++.h> using namespace std; const int maxn=1000; int a[maxn+50]; int n; int main() { scanf("%d",&n); for(int i=0;i<n;++i) scanf("%d",&a[i]); sort(a,a+n); long long ans=0; for(int i=0;i<n;++i){ for(int j=i+1;j<n;++j){ int l=lower_bound(a,a+n,2*a[j]-a[i])-a; int r=lower_bound(a,a+n,3*a[j]-2*a[i])-a; if(a[r]>3*a[j]-2*a[i]) --r; l=max(l,j+1); r=min(r,n-1); if(l>n-1) continue; ans+=r-l+1; } } printf("%lld\n",ans); return 0; }