C++ 算法题：发工资的快乐 (二分查找)

以下是一种可能的 C++ 实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    vector<int> b(m);
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
    }
    
    sort(b.begin(), b.end());
    
    int left = 1, right = n;
    int ans = -1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        int cnt = 0;
        vector<int> happy(n);
        
        for (int i = 0; i < m; ++i) {
            int idx = b[i] - 1;
            happy[idx] = mid;
            cnt += mid;
        }
        
        for (int i = 0; i < n; ++i) {
            if (happy[i] == 0) {
                if (i > 0 && happy[i - 1] > 0) {
                    happy[i] = max(0, happy[i - 1] - 1);
                    cnt += happy[i];
                } else if (i < n - 1 && happy[i + 1] > 0) {
                    happy[i] = max(0, happy[i + 1] - 1);
                    cnt += happy[i];
                }
            }
        }
        
        bool valid = true;
        for (int i = 0; i < n; ++i) {
            if (happy[i] < a[i]) {
                valid = false;
                break;
            }
        }
        
        if (valid) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

该实现使用二分查找来找到满足条件的最小的 k 值。首先，读取输入的 n、m、a 和 b。然后，对 b 进行排序，以便后续的处理。接下来，使用二分查找来尝试不同的 k 值。在每次二分查找的迭代中，首先初始化一个长度为 n 的数组 happy，用于存储每个员工的快乐值。然后，将 b 中的 m 个员工的快乐值设置为 k，并将计数器 cnt 增加 k*m。接下来，遍历数组 happy，将未设置快乐值的员工的快乐值设置为距离最近的已设置快乐值的员工的快乐值减一。然后，检查所有员工的快乐值是否满足其期望值。如果满足，更新 ans，并在二分查找中继续查找更小的 k 值；否则，在二分查找中继续查找更大的 k 值。最后，输出 ans。