L 公司发工资问题 - 最小工资求解

题目描述/n/n今天是 L 公司发工资的一天。/n/n$n$ 名员工排成一排准备领工资，编号为 $1//sim n$，第 $i$ 名员工有一个期望快乐值 $a_i$。/n/n老板非常扣，在这 $n$ 名员工中只选择了 $m$ 名员工 $b_1,b_2,//cdots,b_m$ 发 $k$ 元工资。/n/n员工们都非常具有同理心，不仅自己获得工资时会增加快乐值，当周围的员工获得工资时自己也会增加快乐值。/n/n具体地，当与一名员工 A 距离为 $d$ 的员工获得了工资，A 的快乐值会增加 $//max(0, k - d)$。特别地，如果 A 本身就获得了工资，A 的快乐值会增加 $k$。/n/n老板希望，你能找到最小的整数 $k$，使得所有员工的快乐值不低于他的期望。/n/n## 输入格式/n/n第一行两个整数 $n,m$。/n/n第二行 $n$ 个整数 $a_1,a_2,//cdots,a_n$。/n/n第三行 $m$ 个整数 $b_1,b_2,//cdots,b_m$。/n/n## 输出格式/n/n一个整数，表示你求出的最小的 $k$。/n/n## 样例 #1/n/n### 样例输入 #1/n/n/n5 5/n3 3 3 3 3/n1 2 3 4 5/n/n/n### 样例输出 #1/n/n/n2/n/n/n## 样例 #2/n/n### 样例输入 #2/n/n/n5 2/n5 2 6 3 1/n2 5/n/n/n### 样例输出 #2/n/n/n5/n/n/n## 提示/n/n**【样例说明】/n/n样例 $1$ 中，$k=2$ 时，每个人的快乐值分别为 $3,4,4,4,3$，满足要求。/n/n样例 $2$ 中，$k=5$ 时，每个人的快乐值分别为 $5,7,7,7,7$，满足要求。/n/n【数据范围】/n/n对于 $10//%$ 的数据，满足 $n=1$。/n/n对于 $30//%$ 的数据，满足 $n//le 300$。/n/n对于 $60//%$ 的数据，满足 $n//le 5000$。/n/n对于另外 $10//%$ 的数据，满足 $m=1$。/n/n对于 $100//%$ 的数据，满足 $1//le m//le n//le 10^6$，$0//le a_i//le 10^9$，$1//le b_i//le n$ 且 $b_i$ 互不相同。/n/n本题输入量较大，请注意使用合理的输入方式。/nc++内容：解题思路/n/n首先我们需要找到一个工资的最小值$k$，使得所有员工的快乐值都不低于他们的期望值。我们可以通过二分查找的方法来求解。/n/n设定二分查找的上界为$upper$，初始值为最大期望快乐值$max/_a$，下界为$lower$，初始值为0。/n/n在每次二分查找的过程中，我们假设当前的工资为$mid=(upper+lower)/2$，然后根据当前工资计算每个员工的快乐值。/n/n对于每个员工$i$，计算员工$i$获得工资后的快乐值增加量为$//max(0, mid - d_i)$，其中$d_i$为员工$i$距离离他最近的获得工资的员工的距离。/n/n然后我们计算所有员工的快乐值总和$sum$，如果$sum$大于等于所有员工期望快乐值的总和，说明当前工资$mid$是一个合理的解，我们将工资的上界更新为$mid$。否则，工资的下界更新为$mid+1$。/n/n最终，当上界和下界相等时，我们找到了最小的工资$k$。/n/n时间复杂度分析**/n/n二分查找的时间复杂度为$O(//log n)$，在每次二分查找中，我们需要计算每个员工的快乐值，即需要遍历每个员工。因此，总的时间复杂度为$O(n//log n)$。/n/n代码实现/n/nc++/n#include <iostream>/n#include <vector>/n#include <algorithm>/nusing namespace std;/n/nint main() {/n int n, m;/n cin >> n >> m;/n vector<int> a(n);/n for (int i = 0; i < n; i++) {/n cin >> a[i];/n }/n vector<int> b(m);/n for (int i = 0; i < m; i++) {/n cin >> b[i];/n }/n /n int upper = *max_element(a.begin(), a.end()); // 工资的上界/n int lower = 0; // 工资的下界/n /n while (upper > lower) {/n int mid = (upper + lower) / 2;/n /n // 计算每个员工的快乐值/n vector<int> d(n, INT_MAX);/n for (int i = 0; i < m; i++) {/n d[b[i] - 1] = 0;/n }/n for (int i = 1; i < n; i++) {/n d[i] = min(d[i], d[i - 1] + 1);/n }/n for (int i = n - 2; i >= 0; i--) {/n d[i] = min(d[i], d[i + 1] + 1);/n }/n /n long long sum = 0; // 快乐值总和/n for (int i = 0; i < n; i++) {/n sum += max(0, mid - d[i]) + a[i];/n }/n /n // 根据快乐值总和与期望快乐值的总和的比较结果更新上界或下界/n if (sum >= accumulate(a.begin(), a.end(), 0)) {/n upper = mid;/n } else {/n lower = mid + 1;/n }/n }/n /n cout << upper << endl;/n /n return 0;/n}/n