C Match Points ( Educational Codeforces Round 64 (Rated for
|
You are given a set of points?x1x1,?x2x2,...,?xnxn?on the number line. Two points?ii?and?jj?can be matched with each other if the following conditions hold:
What is the maximum number of pairs of points you can match with each other? Input The first line contains two integers?nn?and?zz?(2≤n≤2?1052≤n≤2?105,?1≤z≤1091≤z≤109) — the number of points and the constraint on the distance between matched points,respectively. The second line contains?nn?integers?x1x1,?x2x2,?xnxn?(1≤xi≤1091≤xi≤109). Output Print one integer — the maximum number of pairs of points you can match with each other. Examples
Input
4 2 1 3 3 7
Output
2
Input
5 5 10 9 5 8 7
Output
1
Note In the first example,you may match point?11?with point?22?(|3?1|≥2|3?1|≥2),and point?33with point?44?(|7?3|≥2|7?3|≥2). In the second example,you may match point?11?with point?33?(|5?10|≥5|5?10|≥5). ? ? #include <iostream> #include <algorithm> #include <cstdio> #include <string> #include <cstring> #include <cstdlib> #include <map> #include <vector> #include <set> #include <queue> #include <stack> #include <cmath> // #define lson rt<<1,l,m #define rson rt<<1|1,m+1,r // #define fi first #define se second #define pb push_back #define pq priority_queue<int> #define ok return 0; #define os(str) cout<<string(str)<<endl; #define gcd __gcd #define mem(s,t) memset(s,t,sizeof(s)) #define debug(a,n) for(int i=0;i<n;i++) cout<<a[i]<<" "; cout<<endl; #define debug1(a,n) for(int i=1;i<=n;i++) cout<<a[i]<<" "; cout<<endl; #define debug02(a,n,m) for(int i=0;i<n;i++) {for(int j=0;j<m;j++) cout<<a[i][j]<<" "; cout<<endl; } #define read11(a,k) for (int i = 1; i <= (int)(k); i++) {cin>>a[i];} #define read02(a,m) for(int i=0;i<n;i++) {for(int j=0;j<m;j++) cin>>a[i][j] ; } #define TLE std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cout.precision(10); using namespace std; inline void NO() { cout<<"NO"<<endl; } inline void YES() { cout<<"YES"<<endl; } const int mxn = 2e5+10; #define oi(x) cout<<x<<endl; #define rep(k) for (int i=0;i<n;i++) #define rep1(j,k) for (int i=j;i<=k; i++) #define per(j,k) for (int i=j;i>=k; i--) //#define per(k) for (int i=k-1;i>=0;i--) #define lli long long string str,ch; lli a[mxn],vis[mxn]; int n,k,ans; int judge(int mid) { for(int i=n-mid,j=0; i<n;i++) { if(a[i]-a[j]<k) { return 0; } else j++; } ans = mid; return 1; } int main() { while(cin>>n>>k) { ans = 0; for(int i=0;i<n;i++) cin>>a[i]; sort(a,a+n); int l = 0,r = n/2,mid; while(l<=r) { mid = l + ( (r-l)>>1 ); //cout<<" +++ "<<ans<<endl; if(judge(mid)) l = mid +1 ; else r = mid - 1; } cout<<ans<<endl; } ok; }
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |