员工工资发放的最优方案 - 优化员工快乐值

题目描述

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

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

老板非常扣，在这 $n$ 名员工中只选择了 $m$ 名员工 $b_1,b_2,\cdots,b_m$ 发 $k$ 元工资。

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

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

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

输入格式

第一行两个整数 $n,m$。

第二行 $n$ 个整数 $a_1,a_2,\cdots,a_n$。

第三行 $m$ 个整数 $b_1,b_2,\cdots,b_m$。

输出格式

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

样例 #1

样例输入 #1

5 5
3 3 3 3 3
1 2 3 4 5

样例输出 #1

2

样例 #2

样例输入 #2

5 2
5 2 6 3 1
2 5

样例输出 #2

5

提示

【样例说明】

样例 $1$ 中，$k=2$ 时，每个人的快乐值分别为 $3,4,4,4,3$，满足要求。

样例 $2$ 中，$k=5$ 时，每个人的快乐值分别为 $5,7,7,7,7$，满足要求。

【数据范围】

对于 $10%$ 的数据，满足 $n=1$。

对于 $30%$ 的数据，满足 $n\le 300$。

对于 $60%$ 的数据，满足 $n\le 5000$。

对于另外 $10%$ 的数据，满足 $m=1$。

对于 $100%$ 的数据，满足 $1\le m\le n\le 10^6$，$0\le a_i\le 10^9$，$1\le b_i\le n$ 且 $b_i$ 互不相同。

**本题输入量较大，请注意使用合理的输入方式。**c++代码内容：```cpp #include #include #include using namespace std;

int main() { int n, m; cin >> n >> m; vector a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector b(m); for (int i = 0; i < m; i++) { cin >> b[i]; }

sort(b.begin(), b.end());

int left = 0, right = 1e9;
int ans = right;

while (left <= right) {
    int mid = (left + right) / 2;
    
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        int idx = lower_bound(b.begin(), b.end(), b[i] - mid) - b.begin();
        cnt += i - idx + 1;
    }
    
    if (cnt >= n) {
        ans = min(ans, mid);
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}

cout << ans << endl;

return 0;

}