2829.k-avoiding 数组的最小总和：贪心（数学公式O(1)算出）

【LetMeFly】2829.k-avoiding 数组的最小总和：贪心（数学公式O(1)算出）

力扣题目链接：https://leetcode.cn/problems/determine-the-minimum-sum-of-a-k-avoiding-array/

给你两个整数 n 和 k 。

对于一个由 不同 正整数组成的数组，如果其中不存在任何求和等于 k 的不同元素对，则称其为 k-avoiding 数组。

返回长度为 n 的 k-avoiding 数组的可能的最小总和。

 

示例 1：

输入：n = 5, k = 4
输出：18
解释：设若 k-avoiding 数组为 [1,2,4,5,6] ，其元素总和为 18 。
可以证明不存在总和小于 18 的 k-avoiding 数组。

示例 2：

输入：n = 2, k = 6
输出：3
解释：可以构造数组 [1,2] ，其元素总和为 3 。
可以证明不存在总和小于 3 的 k-avoiding 数组。 

 

提示：

• 1 <= n, k <= 50

解题方法：贪心

构造一个长度为$n$的数组，数组中任意两数之和不得为$k$，如何构造？

我们可以将数组分成两个部分：小于$k$的部分，大于等于$k$的部分。

• 对于小于$k$的部分：

  有$a$则不能有另外的$k-a$，有$1$则不能有另外的$k-1$。

  那么我们怎么选？当然是选尽可能小的了(贪心)。

  我们从$1$开始，选择$1, 2, 3, \dots, \min(n, \lfloor\frac{k}2\rfloor)$即可。

• 对于大于等于$k$的部分：

  若小于$k$的部分不足$n$个，则还需要选择大于等于$k$的数。

  从$k$开始依次选取就好了，一定不存在另一个正整数与这个数的和为$k$。

尽可能多选小于$k$的部分。附等差数列求和公式$s=\frac{(首项+尾项)\times项数}2$。

• 时间复杂度$O(1)$
• 空间复杂度$O(1)$

AC代码

C++

/*
 * @Author: LetMeFly
 * @Date: 2025-03-26 13:08:18
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-26 13:43:41
 */
/*
5 4
1 2 4 5 6

2 6
1 2

∞ 1
1

∞ 2
1 2

∞ 3
1 3

∞ 4
1 2

∞ 5
1 2

∞ 6
1 2 3

∞ 7
1 2 3

∞ 8
1 2 3 4

∞ 9
1 2 3 4

小于k的数最多从1加到k/2(下取整)
之后就可以从k开始k, k+1, k+2, ...了
*/
class Solution {
public:
    int minimumSum(int n, int k) {
        int to = min(n, k / 2);
        int ans = to * (to + 1) / 2;
        n -= to;
        ans += n * (k + k + n - 1) / 2;
        return ans;
    }
};

Python

'''
Author: LetMeFly
Date: 2025-03-26 13:45:41
LastEditors: LetMeFly.xyz
LastEditTime: 2025-03-26 13:47:07
'''
class Solution:
    def minimumSum(self, n: int, k: int) -> int:
        to = min(n, k // 2)
        n -= to
        return to * (to + 1) // 2 + n * (k + k + n - 1) // 2

Java

/*
 * @Author: LetMeFly
 * @Date: 2025-03-26 13:48:53
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-26 13:48:58
 */
class Solution {
    public int minimumSum(int n, int k) {
        int to = Math.min(n, k / 2);
        n -= to;
        return to * (to + 1) / 2 + n * (k + k + n - 1) / 2;
    }
}

Go

/*
 * @Author: LetMeFly
 * @Date: 2025-03-26 13:50:19
 * @LastEditors: LetMeFly.xyz
 * @LastEditTime: 2025-03-26 13:50:45
 */
package main

func minimumSum(n int, k int) int {
    to := min(n, k / 2)
    n -= to
    return to * (to + 1) / 2 + n * (k + k + n - 1) / 2
}

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源