solid-meme/MRT.c at master · sm2bhat/solid-meme · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
//Solving MRT question using binary search + merge sort
#include <stdio.h>
long long int s;
void merge(long long int a[1000000],long long int p,long long int q,long long int r);

void mergeSort(long long int a[1000000],long long int p,long long int r)
{
    long long int q;
    if(p < r)
    {
        q = (p + r) / 2;
        mergeSort(a, p, q);
        mergeSort(a, q+1, r);
        merge(a, p, q, r);
    }
}


void merge(long long  int a[1000000],long long int p,long long int q,long long int r)
{
    long long int b[s],i, j, k;
    k = 0;
    i = p;
    j = q + 1;
    while(i <= q && j <= r)
    {
        if(a[i] < a[j])
        {
            b[k++] = a[i++];
        }
        else
        {
            b[k++] = a[j++];
        }
    }

    while(i <= q)
    {
        b[k++] = a[i++];
    }

    while(j <= r)
    {
        b[k++] = a[j++];
    }

    for(i=r; i >= p; i--)
    {
        a[i] = b[--k];
    }
}

int main()
{
	long long int array[100050],difference[100050];
	long long int w,i,j,t,ans,count;
	scanf("%lld",&t);
	for(i=0;i<t;i++)
	{
		scanf("%lld%lld",&w,&s);
		for(j=0;j<s;j++)
		{
			scanf("%lld",&array[j]);
			if(j)
				difference[j]=array[j]-array[j-1]-1;
			else
				difference[0]=0;
		}

		//for(j=0;j<s;j++)
			//printf("%lld ",difference[j]);
		//printf("\n");

		mergeSort(difference,0,s-1);

		//for(j=0;j<s;j++)
			//printf("%lld ",difference[j]);
		//printf("\n");

        ans=difference[s-w+1];
        printf("%lld\n",ans);
	}
	return 0;
}