pairs

http://acm.hdu.edu.cn/showproblem.php?pid=5178

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4888    Accepted Submission(s): 1758

Problem Description
John has n points on the X axis, and their coordinates are (x[i],0),(i=0,1,2,…,n−1). He wants to know how many pairs<a,b> that |x[b]−x[a]|≤k.(a<b)
 
Input
The first line contains a single integer T (about 5), indicating the number of cases.
Each test case begins with two integers n,k(1≤n≤100000,1≤k≤109).
Next n lines contain an integer x[i](−109≤x[i]≤109), means the X coordinates.
 
Output
For each case, output an integer means how many pairs<a,b> that |x[b]−x[a]|≤k.
 
Sample Input
2
5 5
-100
0
100
101
102
5 300
-100
0
100
101
102
 
Sample Output
3
10
 
Source
 
Recommend
hujie   |   We have carefully selected several similar problems for you:  6447 6446 6445 6444 6443 
 

二分水题

 #include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <set>
#include <map>
typedef long long ll;
#define maxn 100005
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
using namespace std; ll n,k;
ll a[maxn]; int main(){ int T;
while(cin>>T){
while(T--){
cin>>n>>k;
for(int i=;i<=n;i++){
cin>>a[i];
}
sort(a+,a+n+);
ll ans=;
int p;
for(int i=;i<=n;i++){
p=lower_bound(a+,a+i,a[i]-k)-a;
ans+=i-p;
} cout<<ans<<endl;
}
} }

最新文章

  1. Python Day6
  2. 解决Get请求的长度限制
  3. toggle函数
  4. Merge Into
  5. nginx 一二事(3) - 反向代理以及负载均衡
  6. Embedded System.
  7. 集合-Collection
  8. ecshop后台限制IP登录
  9. JVM报错提示
  10. GoF 设计模式:浅浅印象
  11. 08 Noise and Error
  12. 【Spring 核心】装配Bean(一) 自动化装配
  13. Zepto中的Swipe事件失效
  14. SQL 百万级数据提高查询速度的方法
  15. HttpServlet的转发和重定向
  16. iOS基础知识之多态问题
  17. EL(表达式语言)
  18. python学习笔记14-函数
  19. Django介绍(2)
  20. spring---transaction(3)---源代码分析(事务的管理器PlatformTransactionManager)

热门文章

  1. ASP.NET Web Pages:目录
  2. mysqldump备份脚本---待完善
  3. 使用xmlHttprequest有感
  4. AFNetworkingErrorDomain 错误解决方法
  5. MySQL数据库索引(中)
  6. RESTful API &amp; Swagger入门
  7. python3调用C动态库
  8. faker模块基本用法
  9. 3.纯 CSS 创作一个容器厚条纹边框特效
  10. OpenACC 云水参数化方案