pastebin

Paste Search Dynamic
Recent pastes
canAllCPlace
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. bool canAllCPlace(vector<int>& stalls, int d, int c){
  5.         int count, prev;
  6.  
  7.         count = 1;
  8.         prev = stalls[0];
  9.         for(int i = 1; i < stalls.size(); i++){
  10.                 if(stalls[i] - prev >= d){
  11.                         count++;
  12.                         prev = stalls[i];
  13.                 }
  14.                 if(count == c){
  15.                         break;
  16.                 }
  17.         }
  18.  
  19.         if(count < c) return false;
  20.         else return true;
  21. }
  22.  
  23. int main() {
  24.         int tests;
  25.  
  26.         cin >> tests;
  27.  
  28.         while(tests--){
  29.                 int n, c, val, low, diff, high, mid;
  30.                 vector<int> stalls;
  31.                 bool res1, res2;
  32.  
  33.                 cin >> n >> c;
  34.                 for(int i = 0; i < n; i++){
  35.                         cin >> val;
  36.                         stalls.push_back(val);
  37.                 }
  38.                 sort(stalls.begin(), stalls.end());
  39.                 // for(int i = 0; i < n; i++){
  40.                 //      cout << stalls[i];
  41.                 // }
  42.  
  43.                 //find low
  44.                 low = int_max;
  45.                 for(int i = 1; i < n; i++){
  46.                         diff = stalls[i] - stalls[i-1];
  47.                         if(low > diff){
  48.                                 low = diff;
  49.                         }
  50.                 }
  51.  
  52.                 //find high
  53.                 high = stalls[n-1] - stalls[0];
  54.  
  55.                 //binary search
  56.                 while(low <= high){
  57.                         mid = (low + high) / 2;
  58.                         //cout << "d=" << mid << "n";
  59.                         res1 = canAllCPlace(stalls, mid, c);
  60.                         if (!res1){
  61.                                 high = mid - 1;
  62.                         }
  63.                         else{
  64.                                 res2 = canAllCPlace(stalls, mid+1, c);
  65.                                 if (!res2){
  66.                                         cout << mid;
  67.                                         break;
  68.                                 }
  69.                                 else{
  70.                                         low = mid + 1;
  71.                                 }
  72.                         }
  73.                 }
  74.         }
  75.  
  76.         return 0;
  77. }
Parsed in 0.009 seconds