【算法笔记】员工派遣

⚙️ 基本设定1. 规则描述派遣员工去代号为 x 和 y 的两个国家分别要派 cntx 名和 cnty 名员工。每个员工有一个员工号从 1 开始连续增长。从工号 1 到 k 中选择员工派遣。工号为 x 的倍数的不能去 x 国工号为 y 的倍数的不能去 y 国。2. 输入描述输入四个整数依次表示 xycntxcnty。x 和 y 必须为质数。1 x y 300001 cntx, cnty 10^93. 输出描述输出满足条件最小的 k。 重点解析1. 数学逻辑分析根据容斥原理计算基本参数两个集合不能去 x 国的人数A k / x不能去 y 国的人数B k / y都不能去的人数C k / (x * y)专用名额x 国的专用名额B - C k / y - k / (x * y)y 国的专用名额A - C k / x - k / (x * y)公共名额k - A - B C总体思路假定一个 k先让两国消耗尽专用名额再计算公共名额的需求量。比较公共名额与需求量的大小判断 k 是否合适。2. 求最优解的二分法用二分法寻找 k根据题设范围设置左右指针。若公共名额大于需求量说明 k 值过大要收缩右指针反之说明 k 值过小要拉高左指针。二分法要点while (left right)左闭右闭区间指针相等时依旧有意义。先更新中点再用中点进行条件判断。满足题设条件下记录中点值然后选择要继续操作的区间if(满足条件但可能不是最优解){kmid;// 在满足的条件下就可以记录结果尽管可能不是最优解rightmid-1;}else{leftmid1;} 代码实现importjava.util.Scanner;publicclassEmployeeDispatch{publicstaticvoidmain(String[]args){ScannerscannernewScanner(System.in);longxscanner.nextLong();longyscanner.nextLong();longcntxscanner.nextLong();longcntyscanner.nextLong();longleft1;longright2000000000L;// 便于计算右指针初始值longkright;while(leftright){// 更新中点值longmidleft(right-left)/2;// 防止溢出// x 国还需要从“公共名额”中取的人数longneedXMath.max(0,cntx-(mid/y-mid/(x*y)));// y 国还需要从“公共名额”中取的人数longneedYMath.max(0,cnty-(mid/x-mid/(x*y)));// 公共名额总数longcommonmid-mid/x-mid/ymid/(x*y);// 记录中点值然后选择要继续操作的区间if(commonneedXneedY){kmid;rightmid-1;}else{leftmid1;}}System.out.println(k);scanner.close();}}