小欧找数

[题目链接](https://www.nowcoder.com/practice/e821e1ea74a742208a34b4588b2d78e1)

思路

给定两个区间 $[l_1, r_1]$ 和 $[l_2, r_2]$ ，要求有多少个整数 $\textit{mid}$ ，使得存在整数 $x \in [l_1, r_1]$ 和 $y \in [l_2, r_2]$ ，满足 $\textit{mid} = \lfloor \frac{x + y}{2} \rfloor$ 。

转化问题

既然 $x$ 可以取遍 $[l_1, r_1]$ ， $y$ 可以取遍 $[l_2, r_2]$ ，那么 $x + y$ 的取值范围就是连续整数区间 $[l_1 + l_2,\; r_1 + r_2]$ 。

设 $s = x + y$ ，问题变成：当 $s$ 取遍 $[l_1 + l_2,\; r_1 + r_2]$ 中所有整数时， $\lfloor \frac{s}{2} \rfloor$ 能产生多少种不同的值？

关键观察

$\lfloor \frac{s}{2} \rfloor$ 是一个不递减的函数。当 $s$ 从最小值连续增大到最大值时， $\lfloor \frac{s}{2} \rfloor$ 也从最小值连续增大到最大值（每两个连续的 $s$ 值产生同一个 $\lfloor \frac{s}{2} \rfloor$ 值）。

因此， $\lfloor \frac{s}{2} \rfloor$ 的取值是一段连续的整数区间，答案就是：

$ $\lfloor \frac{r_1 + r_2}{2} \rfloor - \lfloor \frac{l_1 + l_2}{2} \rfloor + 1$ $

举例

以样例 $l_1 = 1, r_1 = 3, l_2 = 2, r_2 = 4$ 为例：

$s = x + y$ 的范围是 $[3, 7]$
$\lfloor 3/2 \rfloor = 1$ ， $\lfloor 4/2 \rfloor = 2$ ， $\lfloor 5/2 \rfloor = 2$ ， $\lfloor 6/2 \rfloor = 3$ ， $\lfloor 7/2 \rfloor = 3$
不同的值为 $\{1, 2, 3\}$ ，共 $3$ 个

用公式计算： $\lfloor 7/2 \rfloor - \lfloor 3/2 \rfloor + 1 = 3 - 1 + 1 = 3$ ，一致。

复杂度分析

时间复杂度： $O(1)$ ，只需读入四个数并做一次加法和除法。
空间复杂度： $O(1)$ 。

代码

C++
Java

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long l1, r1, l2, r2;
    cin >> l1 >> r1 >> l2 >> r2;
    long long lo = l1 + l2;
    long long hi = r1 + r2;
    auto floorDiv = [](long long a, long long b) -> long long {
        return a / b - (a % b != 0 && (a ^ b) < 0);
    };
    cout << floorDiv(hi, 2) - floorDiv(lo, 2) + 1 << endl;
    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long l1 = sc.nextLong(), r1 = sc.nextLong();
        long l2 = sc.nextLong(), r2 = sc.nextLong();
        long lo = l1 + l2;
        long hi = r1 + r2;
        System.out.println(Math.floorDiv(hi, 2) - Math.floorDiv(lo, 2) + 1);
    }
}