# 1703

Apr 4th, 2021
89
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. # define ll long long
2. class Solution {
3. public:
4.     int minMoves(vector<int>& nums, int k) {
5.         ll i, n = nums.size(), l, r;
6.         vector<ll> a;   // Indexes array
7.         a.push_back(0); // To make indexes array the same size as prefix array
8.         for(i=0; i<n; i++)
9.             if(nums[i])
10.                 a.push_back(i);
11.         n = a.size();
12.
13.         vector<ll> prefix(n, 0);  // Prefix array
14.         for(i=1; i<n; i++)     // prefix[i] = sum of all elements from a[0] to a[i]
15.             prefix[i] = prefix[i - 1] + a[i];
16.
17.         ll ans = LONG_LONG_MAX;
18.
19.         // Rolling window [l...r] of length k
20.         for(l=1,r=k; r<n; ++l, ++r) {
21.             ll mid = (l + r) / 2;  // Mid-point - current element
22.             ll radius = mid - l;   // How many elements on each side
23.             ll right = prefix[r] - prefix[mid];     // Prefix of radius elements to the right of mid
24.             ll left = prefix[mid - 1] - prefix[l - 1];  // Prefix of radius elements to the left of mid
25.             ll subtract = (radius) * (radius + 1);  // Once all elements are equal, make it a sequence
26.             if(k % 2 == 0) {        // Special case if k is even
27.                 subtract += (a[mid] + (radius + 1));     // Deduct current element and also deduct the cost of the furthest right element
28.             }
29.             ans = min(ans, right - left - subtract);
30.         }
31.         return ans;
32.     }
33. };
RAW Paste Data