OPPO 笔试真题 · 2024 秋招 · 研发岗
判题请到牛客原题提交。
小欧有 2 个区间[l1,r1]和[l2,r2]。小欧想知道存在多少个整数mid可以找到两个整数x和y满足mid=⌊2x+y⌋且l1≤x≤r1，l2≤y≤r2。
其中⌊x⌋表示对x下取整。
一行四个整数l1,r1,l2,r2(1≤l1≤r1≤1014,1≤l2≤r2≤1014)。
一行一个整数，表示满足条件的mid数量
输入：
输出：
说明：
当mid=1时，可以找到x=1,y=2。
当mid=2时，可以找到x=2,y=2。
当mid=3时，可以找到x=3,y=3。
其他任意mid都无法找到满足条件的x和y。
题目问的不是「有多少对 (x,y)」，而是「有多少个不同的 mid」。
而 mid=⌊(x+y)/2⌋ 只由 x+y 决定，所以先把两个变量
收缩成一个：令 S=x+y，问题变成「S 能取哪些值，这些值映射出的
mid 有哪些」。
x 在 [l1,r1] 里连续取值，y 在 [l2,r2] 里连续取值，
所以 S 的最小值是 l1+l2，最大值是 r1+r2。
中间没有空洞：固定 x 时，y 从 l2 走到 r2 就已经把
[x+l2, x+r2] 这一整段取遍；x 增加 1，这段区间整体右移 1，
与上一段首尾相接或重叠。因此
S∈[l1+l2, r1+r2]
区间里的每个整数都能取到。
S 每增加 1，⌊S/2⌋ 要么不变、要么增加 1，绝不会跳过
某个整数。既然 S 是从 l1+l2 一格一格走到 r1+r2 的，
mid 的取值就是
mid∈[⌊2l1+l2⌋, ⌊2r1+r2⌋]
答案即这段整数区间的长度：右端点 − 左端点 + 1。
S 为奇数时 mid 是 (S−1)/2，为偶数时是 S/2。相邻两个 S 给出的
mid 最多相差 1，而 S 是连续走过来的，所以每个中间整数都会被某个 S
命中，不需要分奇偶讨论。
import sys
def solve() -> None:
"""所有可能的 x+y 连续铺满一段区间，取两端 floor 后算长度"""
data = sys.stdin.buffer.read().split()
if not data:
return
l1, r1, l2, r2 = (int(x) for x in data[:4])
low = (l1 + l2) // 2 # 最小的 mid
high = (r1 + r2) // 2 # 最大的 mid
sys.stdout.write(str(high - low + 1) + "\n")
if __name__ == "__main__":
solve()
输入 l1=1, r1=3, l2=2, r2=4，于是 S=x+y∈[3,7]：
| S | 3 | 4 | 5 | 6 | 7 |
|---|
| ⌊S/2⌋ | 1 | 2 | 2 | 3 | 3 |
不同的 mid 只有 {1,2,3}，共 3 个。
用公式验证：⌊(3+4)/2⌋−⌊(1+2)/2⌋+1=3−1+1=3，与穷举结果一致。
对应题面的三组解：
- mid=1：x=1, y=2；
- mid=2：x=2, y=2；
- mid=3：x=3, y=3。
| 解法 | 时间复杂度 | 空间复杂度 | 说明 |
|---|
| 枚举 x,y | O((r1−l1+1)(r2−l2+1)) | O(1) | 区间可达 1014，完全不可行 |
| 枚举 S | O(r1+r2−l1−l2) | O(1) | 仍然会超时，但已经是「一维」思路 |
| 公式 | O(1) | O(1) | 直接算两端点，推荐 |
区间 [L,R] 里整数个数是 R−L+1，不是 R−L。
样例里 3−1=2 会输出成 2，正好和正确答案差一。
l,r 上界是 1014，双重循环必然超时。题目只关心 mid 的个数，
而这个个数只和两个端点的和有关。
S 是连续取遍的，取整之后 mid 也连续，不需要分奇偶分类讨论，
也不需要减去重复。
int((l1 + l2) / 2) 在 1014 量级上虽然还能算对，但没必要冒精度风险，
直接用整数除法 // 即可（本题所有数都是正数，// 就是下取整）。
- 如果题目改成 mid=⌈(x+y)/2⌉，结论同样是「连续区间」，
只需把两个端点换成 ⌈⋅⌉：答案是
⌈(r1+r2)/2⌉−⌈(l1+l2)/2⌉+1。 - 如果 x、y 的取值范围不是连续区间（比如只允许偶数），
「S 连续」这个前提就不成立了，需要重新分析取值集合。 - 更一般地，「两个连续整数区间上的线性组合的取值范围还是区间」是很多
计数题的第一步化简，值得记住。
