Aggressive cow

 

  1. #include<iostream>
  2. #include <vector>
  3. #include<string>
  4. #include<queue>
  5. #include<algorithm>
  6. #include <unordered_map>
  7.  
  8. using namespace std;
  9. typedef long long int ll;
  10.  
  11.  
  12. bool possible(vector<int> v, ll mid, ll k) {
  13.  
  14. int last;
  15. int cnt =0;
  16. last = v[0];
  17. cnt++;
  18. for (int i = 1; i < v.size(); i++) {
  19. if (v[i] - last >= mid) {
  20. cnt++;
  21. last = v[i];
  22.  
  23. if (cnt == k) return true;
  24. }
  25. }
  26.  
  27. if (cnt >= k) return true;
  28. else return false;
  29.  
  30.  
  31.  
  32.  
  33. }
  34.  
  35.  
  36. int main() {
  37.  
  38.  
  39. int t;
  40. cin >> t;
  41. while (t--) {
  42.  
  43. int n, k;
  44. cin >> n >> k;
  45.  
  46. vector<int> v(n,0);
  47.  
  48. for (int i = 0; i < n; i++) cin >> v[i];
  49.  
  50. sort(v.begin(), v.end());
  51.  
  52. long long int result;
  53.  
  54.  
  55. ll L = 0;
  56. ll U = v[n - 1] - v[0];
  57.  
  58. while (L <= U) {
  59. ll mid =( L + U) / 2;
  60.  
  61. if (possible(v,k,mid)== true) {
  62.  
  63. result = mid;
  64. L = mid + 1;
  65. }
  66. else {
  67. U = mid-1;
  68. }
  69. }
  70.  
  71. cout << result << endl;
  72.  
  73. }
  74.  
  75. return 0;
  76. }

Comments

Post a Comment

Popular posts from this blog

LRU Cache Implementation

 // LRU Cache implementation #include <iostream> #include <unordered_map> using namespace std; class DLLNode { public: int key; int value; DLLNode *next; DLLNode *prev; DLLNode(int k, int v) { this->key = k; this->prev = NULL; this->value = v; this->next = NULL; } }; //Data structure and globals unordered_map<int, DLLNode*> cache; int Size =0; int capacity; DLLNode * head = new DLLNode(-1, -1); DLLNode * tail = new DLLNode(-1, -1); void addNodeAtHead(DLLNode *node) { node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; return; } void removeNode(DLLNode* node) { DLLNode* prev = node->prev; DLLNode* next = node->next; prev->next = next; next->prev = prev; } int removeFromTail() { DLLNode* temp = tail->prev; removeNode(temp); return temp->key; } void moveToHead(DLLNode *node) { cout << "access this key" << node->key...
Read more

Segmentation Tree

#include< iostream > #include< string > #include< vector > #include< algorithm > using namespace std ; void Build ( int arr [], int segtree [], int s , int e , int index ) {      if ( s == e ) {         segtree [ index ] = arr [ s ];      }      else {          int mid = ( s + e ) / 2 ;         Build ( arr , segtree , s , mid , 2 * index );         Build ( arr , segtree , mid + 1 , e , 2 * index + 1 );          if ( segtree [ 2 * index ] < segtree [ 2 * index + 1 ])             segtree [ index ] = segtree [ 2 * index ];          else    ...
Read more