L 公司发工资：最小工资满足员工期望快乐值

今天是 L 公司发工资的一天。

n 名员工排成一排准备领工资，编号为 1∼n，第 i 名员工有一个期望快乐值 a_i 。

老板非常扣，在这 n 名员工中只选择了 m 名员工 b₁, b₂,⋯,b_m 发 k 元工资。

员工们都非常具有同理心，不仅自己获得工资时会增加快乐值，当周围的员工获得工资时自己也会增加快乐值。

具体地，当与一名员工 A 距离为 d 的员工获得了工资，A 的快乐值会增加 max(0, k-d)。特别地，如果 A 本身就获得了工资，A 的快乐值会增加 k。

老板希望，你能找到最小的整数 k，使得所有员工的快乐值不低于他的期望。

输入格式

第一行两个整数 n,m。

第二行 n 个整数 a₁, a₂,⋯,a_n 。

第三行 m 个整数 b₁, b₂,⋯,b_m 。

输出格式

一个整数，表示你求出的最小的 k。

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(a.begin(), a.end(), greater<int>()); // Sort the employees' happiness values in descending order
    sort(b.begin(), b.end()); // Sort the chosen employees' indices in ascending order
    
    int k = 0;
    for (int i = 0; i < n; i++) {
        if (i < m) {
            k = max(k, a[i] + b[i]);
        }
        else {
            k = max(k, a[i]);
        }
    }
    
    cout << k << endl;
    
    return 0;
}