Two types of 1s that can be picked
I gotta say this is actually a good question, against many of the complaints in the comment section. Though a bit hard to understand, it went beyond typical LC 
I gotta say this is actually a good question, against many of the complaints in the comment section. Though a bit hard to understand, it went beyond typical LC prototypes of questions and requires some mental exercise which is fun.\n\nWe can divide the k ones we are to pick into two categories: those that are already there, and those that have to be created. \n\nSuppose we want to pick k ones from [i,j], in which there a re already m ones, leaving us with max(0,k-m) to be created. It is obvious that the latter part takes 2*(k-m) steps by creating and moving immediately ones on the indices next to the original postion, now let\'s calculate the former ones already there, denoted as f(i,j)\n\nIt is not hard to come up with the idea that all ones should be moved the median of their indices, leaving us with\n\nf(i,j) = Sum(abs(i_1-i_median)) from i to j\n\nthis can actually be calculated using a presum of \'sum of indices of 1\' after we take out the absolute value part.\n\n(Calculate it on paper, without doing the presum it would definitely TLE if you do the brute force sum of the expression)\n\nNext we decide which sections to apply the previous computations to. Suppose we are at position i and we know where to look if we want there a m ones in the previous section.\n\nGreedily it is apparent that we should calculate only sections [i,j] where nums[i]==nums[j]==1 (take notes of appearances of ones with the current presum as key in a dictionary would easily do this), but should all of them be considered?\n\nThere should be some restrictions on the number of ones to be included in the section.\n\nFor the lower side, k - m, the amount of ones to be created, cannot exceed maxChanges. So, min_to_include = max(k - maxChanges,0)\n\nFor the higher half, I used a sort of loose argument which worked, obviously f(i,j) is quadratic in length j-i, and the expression 2k-2m+f(i-j) would simply increase as we elongate the section after a certain point -- so we cut off the loop at where f(i,j)>2*m.\n\nThat would basicaly do it.\n\n# Code\n```python3 []\nclass Solution:\n    def minimumMoves(self, nums: List[int], k: int, maxChanges: int) -> int:\n        if 1 not in nums:return 2*k\n        presum = [0]\n        N = len(nums)\n        presumi = [0]\n        presumc = [0]\n        for i,a in enumerate(nums):\n            presumi.append(presumi[-1]+i*a)\n            presumc.append(presumc[-1]+a)\n        @cache\n        def distomed(a,b):\n            if presum[b+1] - presum[a] == 0:return 0\n            ii = presum[a]+1\n            jj = presum[b]+1\n            kk = (ii+jj) // 2\n            med = inds[kk]\n\n            res = (presumc[med+1] - presumc[a])*med - (presumi[med+1] - presumi[a]) + (presumi[b+1] - presumi[med]) - (presumc[b+1] - presumc[med])*med\n            \n                \n            return res\n        \n        mintoinclude = max(k - maxChanges,0)\n\n        inds = {0:-1}\n        inds_revert = {}\n        res = inf\n        for i,a in enumerate(nums):\n            presum.append(presum[-1]+a)\n            if a == 1:\n                inds[presum[-1]] = i\n                if presum[-1] == 1:\n                    inds[0] = i-1\n                \n            nowsum = presum[-1]\n            toinclude = mintoinclude\n            if toinclude > nowsum:continue\n            while toinclude<=nowsum and toinclude <= k:\n                j = inds[nowsum-toinclude]\n                D = distomed(j+1,i)\n                res = min(res,2*k-2*toinclude+D)\n                if D > 2*toinclude:break\n                toinclude  += 1\n        return res\n            \n\n        \n```
['Python3']