Description

给定一个长度为\(n\)的数组\(a\)和常数\(x\),其中\(a_i\)表示种类为\(i\)的物品价值。

对于物品,存在两种操作:

  • 操作1:花费\(a_i\)的成本,买入一个种类\(i\)的物品。
  • 操作2:花费\(x\)的成本,使所有物品种类\(j\)变动为\((j+1) \% n\)。

现在有\(n\)个物品,每个种类各一件,求全部买入的最小成本。

Constraints

  • \(1 \le n \le 10^3\)
  • \(1 \le a_i \le 10^9\)
  • \(1 \le x \le 10^9\)

Solution

至少有2个结论:

  • 最多执行\(n-1\)次操作2。
  • 第\(r\)次操作2时得到的成本为\(\sum_{i=0}^n min\_cost\_of\_item_i + r \times x\)。

这里的\(item_i\)指的是初始为种类\(i\)的物品,随后第\(k \in [0, r]\)次操作2时会转为种类\((i+k) \% n\)。

因此不断维护\(item_i\)最小值即可。

Code

class Solution {
public:
    long long minCost(vector<int>& nums, int x) {
        using L = long long;
        auto n = nums.size();
        auto ans = numeric_limits<L>::max();
        vector mincosts(n, numeric_limits<int>::max());
        for(int r = 0; r < n; ++r) {
            for(int i = 0; i < n; ++i) {
                mincosts[i] = min<L>(mincosts[i], nums[(i+r) % n]);
            }
            auto cost = accumulate(mincosts.begin(), mincosts.end(), L(r) * x);
            ans = min(ans, cost);
        }
        return ans;
    }
};

LeetCode-2735 Collecting Chocolates