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;
}
};