C. 最长好数组 - 详细题解

问题重述

构造一个严格递增的数组 $a$，满足相邻元素差严格递增，且所有元素在 $[l, r]$ 范围内。求最大可能长度。

---

贪心策略

为了构造最长的好数组，我们应该让数组的增长尽可能慢，这样才能在有限区间 $[l, r]$ 内放入更多元素。

贪心构造方法：

• 第一个元素取最小值：$a_1 = l$
• 第二个元素取 $a_2 = l + 1$（最小可能的增长）
• 第三个元素取 $a_3 = l + 1 + 2 = l + 3$（差值为 $2$）
• 第四个元素取 $a_4 = l + 3 + 3 = l + 6$（差值为 $3$）
• 以此类推...

通项公式

第 $i$ 个元素的值为：

$$a_i = l + \frac{i(i-1)}{2}$$

推导过程：

设 $d_k = a_{k+1} - a_k$ 为相邻差，则 $d_1 = 1, d_2 = 2, d_3 = 3, \dots$

$$\begin{aligned} a_i &= a_1 + d_1 + d_2 + \cdots + d_{i-1} \\ &= l + (1 + 2 + \cdots + (i-1)) \\ &= l + \frac{(i-1)i}{2} \end{aligned} $$

---

正确性证明

引理

贪心构造的数组 $a$ 是最优的，即不存在比它更长的好数组。

证明思路

假设存在另一个好数组 $b$，长度大于 $a$。

由于 $a$ 是贪心构造的（每个位置都取最小可能值），必然存在某个位置 $i$，使得：

• 对于所有 $j < i$，有 $a_j = b_j$
• $a_i < b_i$（因为 $a_i$ 已是最小）

设 $n = \text{len}(a) + 1$ 为 $b$ 的长度（假设只长 $1$），则：

$$b_n - b_{n-1} > b_{n-1} - b_{n-2} \ge a_{n-1} - a_{n-2} $$

这意味着我们可以将 $b_n$ 附加到数组 $a$ 的末尾，构造出更长的数组，与 $a$ 的最大性矛盾。

因此，贪心构造的数组 $a$ 就是最优解。

---

问题转化

由通项公式 $a_n = l + \frac{n(n-1)}{2}$，我们需要找到最大的 $n$ 满足：

$$l + \frac{n(n-1)}{2} \le r$$

令 $b = r - l$，则条件化为：

$$\frac{n(n-1)}{2} \le b$$

即：

$$n(n-1) \le 2b$$

---

求解方法

方法一：解二次不等式

$$n^2 - n - 2b \le 0$$

解方程 $n^2 - n - 2b = 0$：

$$n = \frac{1 + \sqrt{1 + 8b}}{2}$$

因此：

$$n_{\max} = \left\lfloor \frac{1 + \sqrt{1 + 8b}}{2} \right\rfloor $$

方法二：二分查找

二分查找最大的 $n$ 满足 $\frac{n(n-1)}{2} \le b$。

---

算法步骤

1. 读入 $l$ 和 $r$
2. 计算 $b = r - l$
3. 二分查找最大的 $n$ 使得 $\frac{n(n-1)}{2} \le b$
4. 输出 $n$

---

完整代码

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        long long l, r;
        cin >> l >> r;
        
        long long b = r - l;  // 可用的增长空间
        
        // 二分查找最大的 n 满足 n*(n-1)/2 <= b
        long long left = 2, right = 1000000000;
        
        while (left < right) {
            long long mid = (left + right) / 2;
            if (mid * (mid - 1) / 2 <= b) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        cout << left - 1 << endl;
    }
    
    return 0;
}

---

公式解法（更简洁）

#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    
    while (t--) {
        long long l, r;
        cin >> l >> r;
        
        long long b = r - l;
        long long n = (1 + sqrt(1 + 8 * b)) / 2;
        
        cout << n << endl;
    }
    
    return 0;
}

---

时间复杂度

• 二分查找：$O(\log r)$ 每个测试用例
• 公式解法：$O(1)$ 每个测试用例
• 总复杂度：$O(t \log r)$ 或 $O(t)$

---

示例验证

$l$	$r$	$b = r-l$	$n(n-1)/2 \le b$ 的最大 $n$	输出
1	2	1	$n=2$: $2\times1/2=1 \le 1$ ✓	2
	5	4	$n=3$: $3\times2/2=3 \le 4$ ✓ $n=4$: $4\times3/2=6 > 4$ ✗	3
2		0	$n=1$: $1\times0/2=0 \le 0$ ✓	1
10	20	10	$n=5$: $5\times4/2=10 \le 10$ ✓ $n=6$: $6\times5/2=15 > 10$ ✗	5
1	$10^9$	$10^9-1$	解方程得 $n \approx 44721$	44721

与样例输出完全一致。