2834. 找出美丽数组的最小和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    static final int MOD = (int)1e9 + 7;
    public int minimumPossibleSum(int n, int target) {
        int m = target / 2;
        if (n <= m) {
            return (int)(((long)1 + n) * n / 2 % MOD);
        } else {
            long firstPart = (((long)(1 + m) * m) / 2 % MOD);
            long secondPart = (((((long) target + target + (n - m) - 1) * (n - m)) / 2) % MOD);
            // System.out.println(firstPart + " " + secondPart);
            return (int)((long)(firstPart + secondPart) % MOD);
        }
    }
}

Quote: lc-2834

复习一下等差数列的求和公式：一个等差数列的和，等于其首项与末项的和，乘以项数除以2。所以从 1 一直加到 n 的和就是 (n + 1) * n / 2。

题目的基本思想是，如果 target = 7, n = 3，那么最优解就是取从 1 到 7 // 2 = 3：[1, 2, 3]，这样的和最小，所以就是取从 1 到 n 的 n 个数，和为 (n + 1) * n / 2。

但也有复杂情况，那就是如果 n > target // 2，例如 target = 7, n = 6，那么这时 [1, 2, 3] 后面如果继续添加元素 4，就会出现 3 + 4 = 7，违反了元素和不能等于 target 的要求，所以下一个元素只能从 target = 7 开始取，才能确保元素和不为 target。也就是需要在 target 起取 n - target//2 个数，最后的数组为 [1 .. target//2] + [target .. target//2 + n]，直接计算和即可。