fork(20) download
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cassert>
  4. #include <cctype>
  5. #include <cmath>
  6. #include <cstdio>
  7. #include <cstdlib>
  8. #include <cstring>
  9. #include <ctime>
  10. #include <deque>
  11. #include <functional>
  12. #include <iomanip>
  13. #include <iostream>
  14. #include <limits>
  15. #include <list>
  16. #include <map>
  17. #include <numeric>
  18. #include <queue>
  19. #include <set>
  20. #include <sstream>
  21. #include <stack>
  22. #include <string>
  23. #include <utility>
  24. #include <vector>
  25.  
  26. using namespace std;
  27.  
  28. #ifndef ONLINE_JUDGE
  29. bool debug = false;
  30. #else
  31. bool debug = true;
  32. #endif
  33.  
  34. typedef vector <int> vi;
  35. typedef pair <int, int> pii;
  36.  
  37. //definition
  38. #define gc() getchar()
  39. #define pc() putchar()
  40.  
  41. #define MOD 1000000007
  42. #define MAX 100005
  43. #define pi 3.14159265358979
  44. #define ESP (1e-9)
  45.  
  46. #define llu long long unsigned
  47. #define lld long long
  48. #define ld long
  49.  
  50. #define fu(i,a,n) for(i=a;i<n;i++)
  51. #define fue(i,a,n) for(i=a;i<=n;i++)
  52. #define fd(i,n,a) for(i=n;i>a;i--)
  53. #define fde(i,n,a) for(i=n;i>=a;i--)
  54. #define fr(i,a) for(i=0;i<a;i++)
  55. #define fe(i,a) for(i=0;i<=a;i++)
  56.  
  57. #define sf_d(n) scanf("%d",&n)
  58. #define sf_ld(n) scanf("%ld",&n)
  59. #define sf_lld(n) scanf("%lld",&n)
  60.  
  61. #define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
  62. #define all(vi) vi.begin(), vi.end()
  63. #define len length()
  64. #define pb push_back
  65. #define sz size()
  66. #define mp make_pair
  67. #define clr clear()
  68. #define ff first
  69. #define ss second
  70. #define imax numeric_limits<int>::max()
  71. #define imin numeric_limits<int>::min()
  72. #define ldmax numeric_limits<ld>::max()
  73. #define ldmin numeric_limits<ld>::min()
  74. #define lldmax numeric_limits<lld>::max()
  75. #define lldmin numeric_limits<lld>::min()
  76. //end of definition
  77.  
  78. //fast input
  79.  
  80. int scan_d() {register int c=gc();int x=0;for(;(c<48 || c>57);c = gc());for(;c>47 && c<58;c = gc()){x = (x<<1) + (x<<3) + c - 48;}return x;}
  81. ld scan_ld() {int ip=getchar(),flag=1;ld ret=0;for(;ip<'0'||ip>'9';ip=getchar())if(ip=='-'){flag=-1;ip=getchar();break;}for(;ip>='0'&&ip<='9';ip=getchar())ret=ret*10+ip-'0';return flag*ret;}
  82. lld scan_lld() {int ip=getchar(),flag=1;lld ret=0;for(;ip<'0'||ip>'9';ip=getchar())if(ip=='-'){flag=-1;ip=getchar();break;}for(;ip>='0'&&ip<='9';ip=getchar())ret=ret*10+ip-'0';return flag*ret;}
  83. llu scan_llu() {int ip=getchar();llu ret=0;for(;ip<'0'||ip>'9';ip=getchar());for(;ip>='0'&&ip<='9';ip=getchar())ret=ret*10+ip-'0';return ret;}
  84.  
  85. //end of fast input
  86.  
  87. //fast output
  88.  
  89. //no line break
  90. void print_d(int n) {if(n<0){n=-n;putchar('-');}int i=10;char output_buffer[10];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<10);}
  91. void print_ld(ld n) {if(n<0){n=-n;putchar('-');}int i=11;char output_buffer[11];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<11);}
  92. void print_lld(lld n) {if(n<0){n=-n;putchar('-');}int i=21;char output_buffer[21];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<21);}
  93. void print_llu(llu n) {int i=21;char output_buffer[21];do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<21);}
  94.  
  95. //new line
  96. void println_d(int n) {if(n<0){n=-n;putchar('-');}int i=10;char output_buffer[11];output_buffer[10]='\n';do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<11);}
  97. void println_ld(ld n) {if(n<0){n=-n;putchar('-');}int i=11;char output_buffer[12];output_buffer[11]='\n';do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<12);}
  98. void println_lld(lld n) {if(n<0){n=-n;putchar('-');}int i=21;char output_buffer[22];output_buffer[21]='\n';do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<22);}
  99. void println_llu(llu n) {int i=21;char output_buffer[22];output_buffer[21]='\n';do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<22);}
  100.  
  101. //special char
  102. char sp;
  103. void printsp_d(int n) {if(n<0){n=-n;putchar('-');}int i=10;char output_buffer[11];output_buffer[10]=sp;do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<11);}
  104. void printsp_ld(ld n) {if(n<0){n=-n;putchar('-');}int i=11;char output_buffer[12];output_buffer[11]=sp;do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<12);}
  105. void printsp_lld(lld n) {if(n<0){n=-n;putchar('-');}int i=21;char output_buffer[22];output_buffer[21]=sp;do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<22);}
  106. void printsp_llu(llu n) {int i=21;char output_buffer[22];output_buffer[21]=sp;do{output_buffer[--i]=(n%10)+'0';n/=10;}while(n);do{putchar(output_buffer[i]);}while(++i<22);}
  107.  
  108. //end of fast output
  109.  
  110.  
  111. int ar[100001],n,c;
  112.  
  113.  
  114. int fnc(int x)
  115. {
  116. int i,temp;
  117. temp=1;
  118. lld prev;
  119. prev=ar[0];
  120. fu(i,1,n)
  121. {
  122. if(ar[i]-prev>=x)
  123. {
  124. temp++;
  125. if(temp==c)
  126. return 1;
  127. prev=ar[i];
  128. }
  129. }
  130. return 0;
  131. }
  132.  
  133.  
  134. void binsearch()
  135. {
  136. int l,r,mid;
  137. l=0;
  138. r=ar[n-1];
  139. while(l<r)
  140. {
  141. mid=(l+r)/2;
  142. if(fnc(mid)==1)
  143. l=mid+1;
  144. else
  145. r=mid;
  146. }
  147. println_lld(l-1);
  148. }
  149.  
  150. int main()
  151. {
  152. /* freopen("input.txt", "r", stdin);
  153.   freopen("output.txt", "w", stdout);*/
  154. lld t,i;
  155. t=scan_lld();
  156. while(t--)
  157. {
  158. n=scan_d();
  159. c=scan_d();
  160. fr(i,n)
  161. ar[i]=scan_d();
  162. sort(ar,ar+n);
  163. binsearch();
  164. }
  165. return 0;
  166. }
Success #stdin #stdout 0s 3860KB
stdin
1
5 3
1
2
8
4
9
stdout
3