[Java/C++/Python] Minimum Distance of Points
Intuition 1\nThe cost of using operation 1 to pick 1, is 2.\nThe cost of using operation 2 to pick 1, is the distance to that 1.\n\n\n# Intuition 2\ni - 1, i, i
# **Intuition 1**\nThe cost of using operation 1 to pick 1, is 2.\nThe cost of using operation 2 to pick 1, is the distance to that 1.\n<br>\n\n# **Intuition 2**\n`i - 1, i, i + 1`, at most 3 places have diatance `<= 2`.\nWe will at most take `m + 3` of 1 using operation 2,\n\nand also,\n`m <= n`, where we have `n` of 1 at the begin.\n`m <= k`, where need `k` of 1.\n<br>\n\n# **Explanation**\nNow the question is simple,\nwhat\'s the minimum distance from `m` points in `A`?\n\nWe choose the center of `m` points as initial index,\nand calculate the total distance with prefix skill.\n\nReturn the minimum result in the end.\n<br>\n\n# **Complexity**\nTime `O(n)`\nSpace `O(n)`\n<br>\n\n**Java**\n```java\n    public long minimumMoves(int[] nums, int k, int maxChanges) {\n        List<Long> A = new ArrayList<>();\n        A.add(0L);\n        for (int i = 0; i < nums.length; i++)\n            if (nums[i] > 0)\n                A.add(A.get(A.size() - 1) + i);\n\n        int n = A.size() - 1, m = Math.max(0, k - maxChanges);\n        long res = Long.MAX_VALUE;\n        for (int l = m; l <= Math.min(n, Math.min(m + 3, k)); l++) {\n            for (int i = 0; i <= n - l; i++) {\n                int mid1 = i + l / 2, mid2 = i + l - l / 2;\n                long cur = A.get(i + l) - A.get(mid2) - (A.get(mid1) - A.get(i));\n                res = Math.min(res, cur + (k - l) * 2);\n            }\n        }\n        return res;\n    }\n```\n\n**C++**\n```cpp\n    long long minimumMoves(vector<int>& nums, int k, int maxChanges) {\n        vector<long long> A = {0};\n        for (int i = 0; i < nums.size(); ++i)\n            if (nums[i] > 0)\n                A.push_back(A.back() + i);\n        int n = A.size() - 1, m = max(0, k - maxChanges);\n        long long res = 1e10;\n        for (int l = m; l <= min(n, min(m + 3, k)); ++l) {\n            for (int i = 0; i <= n - l; ++i) {\n                int mid1 = i + l / 2, mid2 = i + l - l / 2;\n                long long cur = A[i + l] - A[mid2] - (A[mid1] - A[i]);\n                res = min(res, cur + (k - l) * 2);\n            }\n        }\n        return res;\n    }\n```\n\n**Python**\n```py\n    def minimumMoves(self, A: List[int], k: int, maxChanges: int) -> int:\n        A = [i for i,a in enumerate(A) if a]\n        n = len(A)\n        A = [0] + list(accumulate(A))\n        m = max(0, k - maxChanges)\n        res = inf\n        for m in range(m, min(n, m + 3, k) + 1):\n            for i in range(n - m + 1):\n                cur = (A[i + m]) - A[i + m - m // 2] - (A[i + m // 2] - A[i])\n                res = min(res, cur + (k - m) * 2)\n        return res\n```\n
['C', 'Python', 'Java']