#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
int n, m, x, y;
bool check(LL h){
LL a = h / y - h / x / y;
LL b = h / x - h / x / y;
LL c = h - h / x - h / y + h / x / y;
LL s1 = max(0ll, n - a), s2 = max(0ll, m - b);
return s1 + s2 <= c;
}
int main(){
scanf("%d%d%d%d", &n, &m, &x, &y);
int l = 1, r = 2e9;
while(l < r){
int mid = l + (r - l) / 2;
if(check(mid)) r = mid;
else l = mid + 1;
}
printf("%d", l);
return 0;
}
这个问题实际上是一道编程题目,涉及数学与算法的结合使用。它要求我们找出最小的楼层数H,以满足给定的约束条件。这里的核心约束包括两头奶牛(贝茜和贝蒂)不喜欢的楼层编号(即能被特定质数整除的编号),以及他们各自需要的楼层数量。
解决这个问题的关键在于理解以下几个概念:
-
楼层编号能被x整除的数量,表示贝茜不能接受的楼层数量。
-
楼层编号能被y整除的数量,表示贝蒂不能接受的楼层数量。
-
楼层编号同时能被x和y整除的数量,表示既不能分配给贝茜也不能分配给贝蒂的楼层数量。
分析
对于楼层H,可以通过以下步骤来检查是否满足条件:
计算在H层中,编号能被x整除的楼层数量a。
计算在H层中,编号能被y整除的楼层数量b。
计算在H层中,编号同时能被x和y整除的楼层数量c。
确定不能分配给任何一头奶牛的楼层数量c。
根据上述计算,确定剩余可以分配的楼层数量是否足够满足N + M的要求。
实现思路
使用二分查找方法来确定满足条件的最小H值。设定初始的楼层数搜索范围,如l = 1
(最小可能的楼层),r = 2 * 10^9
(一个足够大的楼层数,以保证能包含解)。
在二分查找过程中,计算中间值mid,然后根据上述步骤检查mid是否满足条件。
如果满足条件,则尝试寻找更小的H,即减小r的值。否则,增大l的值以寻找更大的楼层数。
当l和r相遇或交叉时,搜索结束,此时的l(或r)即为所求的最小可能的楼层数H。
输入样例1的输出解释:为了满足条件,最少需要5层楼,因为1, 2, 4层可以分配给贝茜,3层可以分配给贝蒂,而5层没有特殊限制可以分配给任一方。
输入样例2的输出解释:最少需要4层楼,因为1, 4层可以分配给贝茜,而2, 3层可以分配给贝蒂。
这种问题的关键在于理解题目条件,然后将这些条件转换为算法中的数学计算和逻辑判断。二分查找在这类问题中是一个非常有效的工具,因为它允许我们在一个大范围内快速缩小搜索范围,找到满足条件的最优解。
在这个具体的场景中,我们正在处理的问题涉及到在一定条件下分配楼层给两头奶牛,贝茜和贝蒂,同时考虑他们对楼层编号的偏好。我们需要计算为了满足这两头奶牛的需求,楼需要最少建多少层。在代码中,LL s1 = max(0ll, n - a), s2 = max(0ll, m - b);
这行代码的作用是核心的一步,用于计算在满足特定条件下,为每头奶牛保留足够的楼层数量。
解释LL s1 = max(0ll, n - a), s2 = max(0ll, m - b);
n 和 m 分别代表贝茜和贝蒂要求的楼层数量。
a 是在考虑楼层总数 H 时,能被质数 x 整除的楼层数量,即贝茜不接受的楼层数量。
b 是在考虑楼层总数 H 时,能被质数 y 整除的楼层数量,即贝蒂不接受的楼层数量。
max(0ll, n - a)
和 max(0ll, m - b)
分别计算在除去不被接受的楼层后,贝茜和贝蒂还需要的最小楼层数量。如果计算结果为负数(即a或b大于n或m),则说明在除去不喜欢的楼层后,仍有足够的楼层可以满足需求,此时需求变为0。
为何需要max(0ll, ...)
?
这一步骤保证了我们不会因为一个奶牛对楼层的偏好而结束在一个负数的需求上,负数在这里没有实际意义。它确保了无论a或b的值如何,我们计算出的n和m的剩余需求量不会小于0。这是因为如果一个奶牛已经有足够的楼层满足她的要求(甚至在去掉她不喜欢的楼层之后),我们就不需要再为她分配更多的楼层。
总结
在问题的这一步,我们计算每头奶牛实际上还需要多少楼层满足她们的需求。这个计算基于去掉了每头奶牛不喜欢的、即不能被相应质数x或y整除的楼层后的剩余需求。这种方法是寻找问题解决方案的一个关键步骤,因为它直接关系到确定最小楼层总数H的决策过程。