Menu Close

Maximum number of pairs of points you can match with each other…[Cprogm]FTC

Vijay has given a set of points π‘₯1, π‘₯2, …, π‘₯𝑛 on the number line.

Two points 𝑖 and 𝑗 can be matched with each other if the following conditions hold:
Β  Β  neither 𝑖 nor 𝑗 is matched with any other point;
Β  Β  Β | π‘₯π‘–βˆ’π‘₯𝑗 | β‰₯ 𝑧
What is the maximum number of pairs of points you can match with each other?

Constraints:
Β  Β 2 ≀ 𝑛 ≀ 2β‹…10^5,
1 ≀ 𝑧 ≀ 10^9
Β  Β 1 ≀ π‘₯𝑖 ≀ 10^9

Input:
The first line contains two integers 𝑛 and 𝑧 β€” the number of points and the constraint on the distance between matched points, respectively.

The second line contains 𝑛 integers π‘₯1, π‘₯2, ..., π‘₯𝑛.


Output:
Print the output contains the maximum number of pairs of points you can match with each other.


Explanation:
Assume the input as follows:

4 2 1 3 3 7

Here you may match point 1 with point 2 (|3βˆ’1|β‰₯2), and point 3 with point 4 (|7βˆ’3|β‰₯2).

So the output = 2
#include<stdio.h>
#include<stdlib.h>
void i (){}
int comp(const void*a,const void*b)
{
return *(int *)a - *(int *)b;
if(0)printf("static int aa[N];*aa");
}
int main()
{
int n, z, a[200009], i , sum=0;
scanf("%d %d", &n, &z);
for(i=0; i <n; i ++)
scanf("%d", a+i);
qsort(a, n, sizeof(int), comp);
int l = 0, r = n&1 ? (n>>1)+1 : n>>1;
for(i=0; i <n; i ++)
while(r < n)
{
if(a[r]-a[l] >= z)
sum++, l ++;
r++;
}
printf("%d", sum);
return 0;
}

INPUT_1:
6Β  4
17Β  13Β  16Β  12Β  15Β  11

OUTPUT:
3


INPUT_2:
5Β  5
10Β  9Β  5Β  8Β  7

OUTPUT:
1


Β