2834. Find the Minimum Possible Sum of a Beautiful Array

Simulation(TLE)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    private static final int MOD = 1000000007;

    public int minimumPossibleSum(int n, int target) {
        // 大于等于 target 的数字是安全的
        // 小于 target 的数字收集时需要判断另一个数字是否已被收集

        // 反向思考，先把 n 个数的和收集，然后贪心减去和为 target 的大数，最后补齐数字个数
        long sum = ((long) n) * (n + 1) / 2; // sum: 1...n
        sum %= MOD;
        int supplement = n + 1;
        for (int num = Math.min(n, target - 1); num > 0; num--) { // 倒序遍历数组
            int another = target - num;
            if (another > 0 && another < num) {
                // 存在和为 target 的数字和，需要丢弃当前数字，补充为更大的数
                sum -= num;
                another = target - supplement;
                while (another > 0 && another < num) {
                    supplement++;
                    another = target - supplement;
                }
                sum += supplement;
                sum %= MOD;
                supplement++;
            } else if (another >= num) {
                break;
            }
        }

        return (int) sum;
    }
}

Math

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    private static final int MOD = 1000000007;

    public int minimumPossibleSum(int n, int target) {
        // 1 2 3 4 5
        int m = target / 2; // m = 2, 注意此时 m 不能为 3, 否则加上之前的 2 就等于 target 了

        if (n <= m) {
            return (int) (((long) n) * (n + 1) / 2 % MOD);
        } else {
            long sum = (((long) m) * (m + 1) / 2 % MOD);
            sum += ((((long) target) + target + n - m - 1) * (n - m) / 2 % MOD);
            return (int) (sum % MOD); // 不要忘记返回前继续取余
        }
    }
}

References

2834. Find the Minimum Possible Sum of a Beautiful Array