leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1775.cpp (1463B)

      1 class Solution {
      2   public:
      3     int minOperations(vector<int> &nums1, vector<int> &nums2) const {
      4         int n = size(nums1), m = size(nums2);
      5         if (6 * n < m || 6 * m < n) return -1;
      6 
      7         const int s1 = accumulate(begin(nums1), end(nums1), 0);
      8         const int s2 = accumulate(begin(nums2), end(nums2), 0);
      9 
     10         if (s1 > s2) swap(nums1, nums2), swap(n, m);
     11 
     12         make_heap(begin(nums1), end(nums1), greater<int>());
     13         make_heap(begin(nums2), end(nums2), less<int>());
     14 
     15         int goal = abs(s1 - s2), res = 0;
     16         while (goal > 0 && !empty(nums1) && !empty(nums2)) {
     17             res++;
     18             if (6 - nums1.front() > nums2.front() - 1) {
     19                 goal -= 6 - nums1.front();
     20                 pop_heap(begin(nums1), end(nums1), greater<int>());
     21                 nums1.pop_back();
     22             } else {
     23                 goal -= nums2.front() - 1;
     24                 pop_heap(begin(nums2), end(nums2), less<int>());
     25                 nums2.pop_back();
     26             }
     27         }
     28 
     29         while (goal > 0 && !empty(nums1)) {
     30             goal -= 6 - nums1.front();
     31             pop_heap(begin(nums1), end(nums1), greater<int>());
     32             nums1.pop_back();
     33             res++;
     34         }
     35 
     36         while (goal > 0 && !empty(nums2)) {
     37             goal -= nums2.front() - 1;
     38             pop_heap(begin(nums2), end(nums2), less<int>());
     39             nums2.pop_back();
     40             res++;
     41         }
     42 
     43         return goal <= 0 ? res : -1;
     44     }
     45 };