Leetcode 2735. Collecting Chocolates

[Woodyiiiiiii]

2735. Collecting Chocolates

2735. Collecting Chocolates

看到时间复杂度，想到可以用O(n^2)的做法。

接下来就是试下直接暴力。从移动次数出发，假设不移动，直接是每个位置对应的cost之和。假设移动一次，如何选择？

首先看下如何计算移动一次和不移动的最小花费：既然要选最小的，还要计算花费，那就有个比较的过程。如何比较？计算获取所有当前巧克力的花费，与之前的进行对比。

class Solution {
    public long minCost(int[] nums, int x) {
        int n = nums.length;
        long ans = Long.MAX_VALUE;

        long[] mns = new long[n];
        Arrays.fill(mns, Long.MAX_VALUE);
        long cost = 0;
        for (int i = 0; i < n; i++) {
            long tmp = 0;
            for (int j = 0; j < n; j++) {
                int idx = (i + j) % n;
                mns[j] = Math.min(mns[j], nums[idx]);
                tmp += mns[j];
            }
            ans = Math.min(ans, cost + tmp);
            cost += x;
        }

        return ans;
    }
}