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