hdu 5178 pairs（BC第一题，，方法不止一种，，我用lower

题意：

X坐标上有n个数。JOHN想知道有多少对数满足：x[a]-x[b]<=k（题意给）[a<b]

思路：

额，，，直接看代码吧，，，，

代码：

int T,n,k;

int x[100005];

int main(){

    cin>>T;

    while(T--){

        cin>>n>>k;

        rep(i,1,n) scanf("%d",&x[i]);

        sort(x+1,x+1+n);

        ll ans=0;

        rep(i,2,n){

            ll temp=x[i]-k;

            int pos=lower_bound(x+1,x+i,temp)-x;

            ans+=(ll)(i-pos);

        }

        printf("%I64d\n",ans);

    }

    return 0;

}

巴特西

hdu 5178 pairs（BC第一题，，方法不止一种，，我用lower_bound那种。。。）

最新文章

热门文章