Skip to content

Latest commit

 

History

History
177 lines (141 loc) · 3.77 KB

README.md

File metadata and controls

177 lines (141 loc) · 3.77 KB
comments difficulty edit_url rating source tags
true
中等
1347
第 359 场周赛 Q2
贪心
数学

2829. k-avoiding 数组的最小总和

English Version

题目描述

给你两个整数 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

解法

方法一：贪心 + 模拟

我们从正整数 $i=1$ 开始，依次判断 $i$ 是否可以加入数组中，如果可以加入，则将 $i$ 加入数组中，累加到答案中，然后将 $k-i$ 置为已访问，表示 $k-i$ 不能加入数组中。循环直到数组长度为 $n$。

时间复杂度 $O(n^2)$，空间复杂度 $O(n^2)$。其中 $n$ 为数组长度。

Python3

class Solution:
    def minimumSum(self, n: int, k: int) -> int:
        s, i = 0, 1
        vis = set()
        for _ in range(n):
            while i in vis:
                i += 1
            vis.add(i)
            vis.add(k - i)
            s += i
        return s

Java

class Solution {
    public int minimumSum(int n, int k) {
        int s = 0, i = 1;
        boolean[] vis = new boolean[k + n * n + 1];
        while (n-- > 0) {
            while (vis[i]) {
                ++i;
            }
            vis[i] = true;
            if (k >= i) {
                vis[k - i] = true;
            }
            s += i;
        }
        return s;
    }
}

C++

class Solution {
public:
    int minimumSum(int n, int k) {
        int s = 0, i = 1;
        bool vis[k + n * n + 1];
        memset(vis, false, sizeof(vis));
        while (n--) {
            while (vis[i]) {
                ++i;
            }
            vis[i] = true;
            if (k >= i) {
                vis[k - i] = true;
            }
            s += i;
        }
        return s;
    }
};

Go

func minimumSum(n int, k int) int {
	s, i := 0, 1
	vis := make([]bool, k+n*n+1)
	for ; n > 0; n-- {
		for vis[i] {
			i++
		}
		vis[i] = true
		if k >= i {
			vis[k-i] = true
		}
		s += i
	}
	return s
}

TypeScript

function minimumSum(n: number, k: number): number {
    let s = 0;
    let i = 1;
    const vis: boolean[] = Array(n * n + k + 1);
    while (n--) {
        while (vis[i]) {
            ++i;
        }
        vis[i] = true;
        if (k >= i) {
            vis[k - i] = true;
        }
        s += i;
    }
    return s;
}