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

{"title":"L公司发工资算法：最小工资满足员工期望快乐值","description":"本文探讨了L公司发工资的算法问题，给定员工期望快乐值和老板发工资的员工名单，需要找到最小的工资金额，使得所有员工的快乐值不低于期望。算法分析和C++代码示例帮助理解问题并提供解决方案。","keywords":"算法，工资，快乐值，期望值，C++，代码，最优解，贪心算法","content":"\u0009\n名员工排成一排准备领工资，编号为\u0009\n1\u0009\u0009\n∼\u0009\n1∼n，第\u0009\n\u0009\ni\u0009\n名员工有一个期望快乐值\u0009\n\u0009\na\u0009\ni\u0009\n\u0009\n。\n\n老板非常扣，在这\u0009\n\u0009\nn\u0009\n名员工中只选择了\u0009\n\u0009\nm\u0009\n名员工\u0009\n\u0009\n1\u0009\n,\u0009\n\u0009\n2\u0009\n,\u0009\n⋯\u0009\n,\u0009\n\u0009\nb\u0009\n1\u0009\n\u0009\n,b\u0009\n2\u0009\n\u0009\n,⋯,b\u0009\nm\u0009\n\u0009\n 发\u0009\n\u0009\nk\u0009\n元工资。\n\n员工们都非常具有同理心，不仅自己获得工资时会增加快乐值，当周围的员工获得工资时自己也会增加快乐值。\n\n具体地，当与一名员工 A 距离为\u0009\n\u0009\nd\u0009\n的员工获得了工资，A 的快乐值会增加\u0009\n\u0009\nmax\u0009\n(\u0009\n0\u0009\n,\u0009\n\u0009\nk\u0009\n−\u0009\n\u0009\nd\u0009\n)max(0,k−d)。特别地，如果 A 本身就获得了工资，A 的快乐值会增加\u0009\n\u0009\nk\u0009\n。\n\n老板希望，你能找到最小的整数\u0009\n\u0009\nk\u0009\n，使得所有员工的快乐值不低于他的期望。\n\n输入格式\n第一行两个整数\u0009\n\u0009\nn,m\u0009\n。\n\n第二行\u0009\n\u0009\nn\u0009\n个整数\u0009\n\u0009\n1\u0009\n,\u0009\n\u0009\n2\u0009\n,\u0009\n⋯\u0009\n,\u0009\n\u0009\na\u0009\n1\u0009\n\u0009\n,a\u0009\n2\u0009\n\u0009\n,⋯,a\u0009\nn\u0009\n\u0009\n。\n\n第三行\u0009\n\u0009\nm\u0009\n个整数\u0009\n\u0009\n1\u0009\n,\u0009\n\u0009\n2\u0009\n,\u0009\n⋯\u0009\n,\u0009\n\u0009\nb\u0009\n1\u0009\n\u0009\n,b\u0009\n2\u0009\n\u0009\n,⋯,b\u0009\nm\u0009\n\u0009\n。\n\n输出格式\n一个整数，表示你求出的最小的\u0009\n\u0009\nk\u0009\n。c++代码内容：cpp\n#include <iostream>\n#include <vector>\n#include <algorithm>\nusing namespace std;\n\nint main() {\n int n, m;\n cin >> n >> m;\n \n vector<int> a(n);\n for (int i = 0; i < n; i++) {\n cin >> a[i];\n }\n \n vector<int> b(m);\n for (int i = 0; i < m; i++) {\n cin >> b[i];\n }\n \n sort(a.begin(), a.end());\n sort(b.begin(), b.end());\n \n int max_happiness = a[n-1];\n int min_salary = b[0];\n \n int k = max(max_happiness, 2 * a[0]);\n \n if (k <= min_salary) {\n cout << k << endl;\n } else {\n cout << -1 << endl;\n }\n \n return 0;\n}\n