FilesExpand file tree

master

/

AGGRCOW.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

61 lines (57 loc) · 1.06 KB

master

/

AGGRCOW.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

61 lines (57 loc) · 1.06 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

// @amitrajitbose

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll validPosition(ll mid, ll arr[], ll n, ll c)

{

ll prev=arr[0]; // assuming leftmost stall will always be taken by a cow

ll count=1;

for(ll i=1;i<n;i++){

if(arr[i]-prev >= mid)

{

count+=1;

prev=arr[i];

}

}

if(count<c)

return 0;

else

return 1;

}

ll largestMinGap(ll arr[], ll n, ll c)

{

ll low=0;

ll high=1000000007; // as per question, masimum value

ll mid,x;

while(low <= high)

{

mid = (low+high)/2;

if(validPosition(mid, arr, n, c)==1)

{

low=mid+1;

x=mid;

}

else

high=mid-1; //reducing the array size

}

return x;

}

int main() {

ll test;

cin >> test;

while(test--)

{

ll n,c,ans;

ll *arr = new ll[100007]; //constructor

cin >> n >> c;

for(ll i=0;i<n;i++)

{

cin >> arr[i];

}

sort(arr,arr+n);

ans = largestMinGap(arr,n,c);

delete [] arr; //destructor

cout << ans << endl;

}

return 0;

}