leetcode2834--找出美丽数组的最小和

1. 题意

求一个序列和。序列$a$满足：

• 大小为$n$
• $\forall 0\le i,j<n,i\ne j,a_i+a_j\ne target$

找出美丽数组的最小和

2. 题解

贪心的构造这个序列。

当$n\le target/2$时，依次累加序列即可。

当$n>target/2$时，从$target$开始累加。

$$\begin{gathered} m=target/2 \\ ans=\{\begin{array}{l}n(n+1)/2n\le m\\ m(m+1)/2+(target+target+n-m-1)(n-m)/2n>m\end{array} \end{gathered}$$

• 代码

class Solution {
public:int minimumPossibleSum(int n, int target) {long long mid = target/2;long long MOD = 1e9+7;long long ans = 0;if (n <= mid) {ans = n % MOD * ((n + 1)%MOD)/2;}else {ans = (mid+1)*mid /2;ans %= MOD;long long cnt = n - mid;ans += (target + (target + cnt - 1)) * (cnt) /2; }// int idx = 1;// int ans = 0;// for (int i = 0; i < n; ++i,++idx) {//     if ( i == mid )//         idx = target;//     ans += idx % MOD;//     ans %= MOD;// }return (int) (ans % MOD); }
};