Description

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

对于物品，存在两种操作：

• 操作1：花费$a_i$的成本，买入一个种类$i$的物品。
• 操作2：花费$x$的成本，使所有物品种类$j$变动为$(j+1)\mathrm{\%}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\mathrm{\_}cost\mathrm{\_}of\mathrm{\_}ite{m}_i+r\times x$。

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

因此不断维护$ite{m}_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;
    }
};

Link

LeetCode-2735 Collecting Chocolates