用C++解决发工资问题：二分查找求最小工资满足员工期望快乐值

///'思路：//n1. 首先，我们需要找到一个合适的范围来搜索最小的整数 k。根据题目给出的条件，快乐值的增加范围在 [0, k] 之间，所以 k 的取值范围为 [0, max(a_1, a_2, ..., a_n)]。//n2. 接下来，我们可以使用二分查找来搜索 k 的最小值。假设当前搜索的范围为 [left, right]，我们可以取中间值 mid = (left + right) / 2。//n3. 对于每个员工 i，如果 a_i <= mid，则该员工的快乐值增加为 k，否则为 max(0, k - (i - b_j))，其中 b_j 为前面已经获得工资的员工编号。//n4. 计算每个员工的快乐值总和，如果总和大于等于所有员工的期望快乐值之和，则说明当前的 k 值合适，可以继续缩小搜索范围为 [left, mid]；否则，需要增大 k，搜索范围为 [mid + 1, right]。//n5. 重复步骤 2 至 4，直到 left 和 right 相等，此时的 left（或 right）即为最小的合适值 k。//n//n代码实现如下：//n//ncpp//n#include <iostream>//n#include <vector>//n#include <algorithm>//n//nusing namespace std;//n//nint main() {//n int n;//n cin >> n;//n vector<int> a(n);//n for (int i = 0; i < n; i++) {//n cin >> a[i];//n }//n//n int left = 0, right = *max_element(a.begin(), a.end());//n int ans = right; // 初始最小值为最大的 a_i//n while (left <= right) {//n int mid = (left + right) / 2;//n vector<int> dp(n + 1, 0); // dp[i] 表示前 i 名员工的快乐值总和//n for (int i = 1; i <= n; i++) {//n dp[i] = dp[i - 1] + mid; // 每个员工的快乐值增加 k//n for (int j = 0; j < i; j++) {//n if (a[i - 1] > mid) {//n dp[i] = max(dp[i], dp[j] + max(0, mid - (i - j - 1))); // 当 a_i > mid，计算快乐值增加的最大值//n }//n }//n }//n if (dp[n] >= accumulate(a.begin(), a.end(), 0)) {//n ans = min(ans, mid);//n right = mid - 1;//n } else {//n left = mid + 1;//n }//n }//n//n cout << ans << endl;//n//n return 0;//n}//n//n//n时间复杂度分析：//n- 初始化阶段，需要遍历一次数组 a，时间复杂度为 O(n)。//n- 二分查找阶段，最多进行 log(max(a_1, a_2, ..., a_n)) 次迭代，每次迭代需要计算一次快乐值总和，时间复杂度为 O(n^2)。//n- 总时间复杂度为 O(n^2 * log(max(a_1, a_2, ..., a_n)))。//n///