题目链接
分析
考虑比 $k$ 小的数
如果将 $1$ 加入数组内，我们就不能选择 $k - 1$；如果将 $2$ 加入数组内，我们就不能选择 $k - 2 \cdots$
以此类推，对于比 $k$ 小的数，我们取其中较小的一半 $1$ 到 $\lfloor\frac{2}{k}\rfloor$
如果 $n > \lfloor\frac{2}{k}\rfloor$ ，剩下的数从 $k$ 开始，取到 $n - \lfloor\frac{2}{k}\rfloor$ 即可
可以直接使用等差数量求和公式得到答案
代码实现
class Solution {
public:
int minimumSum(int n, int k) {
int t = min(k >> 1, n);
int first = (t * (t + 1)) >> 1;
int second = ((k * 2 + n - t - 1) * (n - t)) >> 1;
return first + second;
}
};
复杂度分析
- 时间复杂度：$O(1)$
- 空间复杂度：$O(1)$
