首页 > 代码库 > 【XY1398】孙云球

【XY1398】孙云球

题目大意

给出$N$个数$a_{1}, a_{2}, ..., a_{N}$,定义三元组$(x,y,z)$满足:

$a_{x}<a_{y}<a_{z}$

$a_{y}-a_{x}≤a_{z}-a_{y}≤2*(a_{y}-a_{x})$

求出这样的三元组的个数

$1≤n≤1000$, $1≤a_{i}≤10^{9}$

算法二分STL的妙用

题解

显然直接枚举会超时(虽然卡过是可以的QWQ)

这题可以用二分来做,但是更简单的方法是用STL中的upper_bound和lower_bound函数可以轻松完成~

上界和下界可以通过不等式推出来哦,两个函数的意思可以自行Baidu,然后就直接看代码吧!

(众:不想解释就直说QAQ)

代码

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1005;
int a[N],n,ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n;j++)
            ans += upper_bound(a+1, a+1+n, 3*a[j]-2*a[i])
                 - lower_bound(a+1, a+1+n, 2*a[j]-a[i]);
    printf("%d",ans);
}

 

【XY1398】孙云球