[M数学] lc2834. 找出美丽数组的最小和(数学+找规律+思维)

1. 题目来源

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

2. 题目解析

很能代表 中等 题目的难度和思维过程。

数据量在 1e5 的话，可以哈希表+模拟。

数据量在 1e9 的话，很明显需要使用 O(n) 以下的算法。

一开始考虑的是，有没有一种方法，统计前缀的所有加和的情况，能够在 O(1) 确定当前值，但想了想应该不太现实…

故开始找规律…

---

思路：

• 先考虑，什么情况下可以直接顺序填 1,2,3,4,…x。实际上就是 n <= target / 2 的情况下，因为这个时候，即便顺序填写的中间值，两个最大的和，也无法超过 target，所以就直接顺序填写就行。
• 一个例子搞懂非顺序填写。n = 5, target = 5;
• 则，最理想的是: 1,2,3,4,5 但是发现，(1,4), (2,3) 能够组合成 5 是不满足的。那么调整后就是 ,1,2,5,6,7。
• 思考一下，前半段实际上就是 [1,n / 2]，后半段剩余的话，就是 [target, …]，那么计算结果就是两个等差数列情况了。

找规律的题目，最好能够从 “特殊” 再到 “一般”。

---

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

---

class Solution {
public:
    int minimumPossibleSum(int n, int target) {
        typedef long long LL;
        const int mod = 1e9 + 7;
        int m = target / 2;
        if (n <= m) return 1ll * n * (1 + n) / 2 % mod;
        return (m * (1ll + m) / 2 + 
                (target + target + (n - m - 1ll)) * (n - m) / 2) % mod;
    }
};
1
2
3
4
5
6
7
8
9
10
11