2834. 美しい配列の最小和を見つける#
2 つの正の整数 n と target が与えられます。
配列 nums が次の条件を満たす場合、それは美しい配列と呼ばれます。
- nums.length == n
- nums は互いに異なる正の整数で構成されています。
- 範囲 [0, n-1] 内に、異なる 2 つのインデックス i と j が存在しないように、nums [i] + nums [j] == target となる。
条件を満たす美しい配列の最小和を返し、結果を $10^9+7$ で割った余りを取ります。
例 1：
入力：n = 2, target = 3
出力：4
説明：nums = [1,3]は美しい配列です。
- numsの長さはn = 2です。
- numsは互いに異なる正の整数で構成されています。
- 異なる2つのインデックスiとjが存在せず、nums[i] + nums[j] == 3となりません。
条件を満たす美しい配列の最小和は4であることが証明できます。
例 2：
入力：n = 3, target = 3
出力：8
説明：
nums = [1,3,4]は美しい配列です。
- numsの長さはn = 3です。
- numsは互いに異なる正の整数で構成されています。
- 異なる2つのインデックスiとjが存在せず、nums[i] + nums[j] == 3となりません。
条件を満たす美しい配列の最小和は8であることが証明できます。
例 3：
入力：n = 1, target = 1
出力：1
説明：nums = [1]は美しい配列です。
ヒント：
- $1 <= n <= 10^9$
- $1 <= target <= 10^9$
貪欲法#
class Solution {
public:
int minimumPossibleSum(int n, int target) {
const int mod = 1e9 + 7;
int m = target / 2;
if (n <= m) {
return (long long) (1 + n) * n / 2 % mod;
}
return ((long long) (1 + m) * m / 2 +
((long long) target + target + (n - m) - 1) * (n - m) / 2) % mod;
}
};