class Solution {
public:
long long minimumPossibleSum(int n, int target) {
}
};
8022. 找出美丽数组的最小和
给你两个正整数：n 和 target 。
如果数组 nums 满足下述条件，则称其为 美丽数组 。
nums.length == n.nums 由两两互不相同的正整数组成。[0, n-1] 内，不存在 两个 不同 下标 i 和 j ，使得 nums[i] + nums[j] == target 。返回符合条件的美丽数组所可能具备的 最小 和。
示例 1：
输入：n = 2, target = 3 输出：4 解释：nums = [1,3] 是美丽数组。 - nums 的长度为 n = 2 。 - nums 由两两互不相同的正整数组成。 - 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。 可以证明 4 是符合条件的美丽数组所可能具备的最小和。
示例 2：
输入：n = 3, target = 3 输出：8 解释： nums = [1,3,4] 是美丽数组。 - nums 的长度为 n = 3 。 - nums 由两两互不相同的正整数组成。 - 不存在两个不同下标 i 和 j ，使得 nums[i] + nums[j] == 3 。 可以证明 8 是符合条件的美丽数组所可能具备的最小和。
示例 3：
输入：n = 1, target = 1 输出：1 解释：nums = [1] 是美丽数组。
提示：
1 <= n <= 1051 <= target <= 105原站题解
javascript 解法, 执行用时: 55 ms, 内存消耗: 49.5 MB, 提交时间: 2024-03-08 09:29:04
/**
* @param {number} n
* @param {number} target
* @return {number}
*/
var minimumPossibleSum = function(n, k) {
const m = Math.min(k >> 1, n);
return ((BigInt(m) * BigInt(m + 1) + BigInt(k * 2 + n - m - 1) * BigInt(n - m)) / 2n) % 1_000_000_007n;
};
rust 解法, 执行用时: 1 ms, 内存消耗: 2.1 MB, 提交时间: 2024-03-08 09:28:36
impl Solution {
pub fn minimum_possible_sum(n: i32, target: i32) -> i32 {
let n = n as i64;
let k = target as i64;
let m = n.min(k / 2);
((m * (m + 1) + (n - m - 1 + k * 2) * (n - m)) / 2 % 1_000_000_007) as i32
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 2 MB, 提交时间: 2023-08-28 10:22:27
func minimumPossibleSum(n, k int) int64 {
m := min(k/2, n)
return int64((m*(m+1) + (k*2+n-m-1)*(n-m)) / 2)
}
func min(a, b int) int { if b < a { return b }; return a }
cpp 解法, 执行用时: 0 ms, 内存消耗: 5.8 MB, 提交时间: 2023-08-28 10:22:08
class Solution {
public:
long long minimumPossibleSum(int n, int k) {
long long m = min(k / 2, n);
return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) / 2;
}
};
java 解法, 执行用时: 0 ms, 内存消耗: 38.3 MB, 提交时间: 2023-08-28 10:21:53
class Solution {
public long minimumPossibleSum(int n, int k) {
long m = Math.min(k / 2, n);
return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) / 2;
}
}
python3 解法, 执行用时: 48 ms, 内存消耗: 16.1 MB, 提交时间: 2023-08-28 10:21:42
class Solution:
def minimumPossibleSum(self, n: int, k: int) -> int:
m = min(k // 2, n)
return (m * (m + 1) + (k * 2 + n - m - 1) * (n - m)) // 2