fork download
copy 
  1. #include <cstdio>
  2. #include <algorithm>
  3. #include<iostream>
  4.  
  5. int partition(int *arr, const int left, const int right);
  6. void quicksort(int *arr, const int left, const int right, const int sz);
  7.  
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14. int main(){
  15. int T,N,K,h[20000];
  16.  
  17. std::ios_base::sync_with_stdio(false);
  18. std::cin.tie(NULL);
  19.  
  20. //scanf("%d",&T);
  21.  
  22.         std::cin >> T;
  23.  
  24.  
  25. while(T--){
  26.     //scanf("%d %d",&N,&K);
  27.  
  28.         std::cin >> N ;
  29.         std::cin >>K;
  30.         //cout <<N<<K;
  31.         //cout<<K;
  32.     for(int i = 0;i < N;++i) scanf("%d",&h[i]);
  33.     quicksort(h,0,N-1,N);
  34.  
  35.     int ans = h[K - 1] - h[0];
  36.  
  37.     for(int i = 1;i + K - 1 < N;++i)
  38.         ans = std::min(ans,h[i + K - 1] - h[i]);
  39.  
  40. //printf("%d\n",ans);
  41.  
  42.   std::cout<<ans;
  43. }
  44.  
  45. return 0;
  46. }
  47.  
  48.  
  49. int partition(int *arr, const int left, const int right) {
  50. const int mid = left + (right - left) / 2;
  51. const int pivot = arr[mid];
  52. // move the mid point value to the front.
  53. std::swap(arr[mid],arr[left]);
  54. int i = left + 1;
  55. int j = right;
  56. while (i <= j) {
  57.     while(i <= j && arr[i] <= pivot) {
  58.         i++;
  59.     }
  60.  
  61.     while(i <= j && arr[j] > pivot) {
  62.         j--;
  63.     }
  64.  
  65.     if (i < j) {
  66.         std::swap(arr[i], arr[j]);
  67.     }
  68. }
  69. std::swap(arr[i - 1],arr[left]);
  70. return i - 1;
  71. }
  72.  
  73. void quicksort(int *arr, const int left, const int right, const int sz)
  74. {
  75.  
  76. if (left >= right) {
  77.     return;
  78. }
  79.  
  80. int part = partition(arr, left, right);
  81.  //printf (arr, sz);
  82.  
  83. quicksort(arr, left, part - 1, sz);
  84. quicksort(arr, part + 1, right, sz);
  85. }
  86.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vItolb
problem AMR10G, based on SPOJ submission 18718161 (C++ 5), 2017-02-07 19:01:53
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!