【QED】hhuggo的完美木桶

2025/9/27 13:42:44 来源：https://blog.csdn.net/m0_67724631/article/details/144948403 浏览: 次关键词：【QED】hhuggo的完美木桶

文章目录

题目
- 题目描述
- 输入输出格式
- 数据范围
- 测试样例
- 样例说明
思路
代码
复杂度分析
- 时间复杂度
- 空间复杂度

题目

题目链接🔗

题目描述

总所周知，木桶效应是说一个木桶所能装的水的多少取决于最短的那个木板。现在 $\text{hhuggo}$ 有 $n$ 个木板， $\text{hhuggo}$ 在听了 $\text{kiwi}$ 说的木桶效应后，他想试试将这些木板拼接成一个木桶，但是 $\text{hhuggo}$ 对木桶的样貌有一定的要求，他希望每个木板的长度差异不超过 $k$ ，那么这些木板拼起来的木桶就是完美的。
$\text{hhuggo}$ 想知道，他最后最多能用多少个木板拼成一个完美木桶？

输入输出格式

【输入格式】

测试用例的第一行包含两个整数 $n$ 和 $k$ 。表示有 $n$ 个木板, $\text{hhuggo}$ 对木板长度差异的要求为 $k$ 。

第二行包含非递减的 $n$ 个整数 $a_1,a_2,a_3...,a_n$ ，其中 $a_i$ 是第 $i$ 个木板的长度。

【输出格式】

对于每个测试用例，输出一个整数，表示 $\text{hhuggo}$ 最多能用到的木板数量。

数据范围

$\le n \le 1 \times 10^4$

$\le k \le 1 \times 10^6$

$\le a_1 \le ... \le a_i \le ... \le a_n \le 1 \times 10^8$

测试样例

input1

10 5
1 4 14 17 18 19 19 26 26 29

output1

input2

6 5
1 2 10 12 15 17

output2

样例说明

在第一个样例中， $\text{hhuggo}$ 最多能用长度为 14,17,18,19,19 这 5 个木板。

思路

简明题意

给出一个不下降数组，在数组中选m个元素，并且满足这m个元素极差小于等于k，求m的最大值。

关键点：因为数组是非递减的，我们只需要选取数组中连续的区间，使得这个区间内的最大值和最小值的差小于等于 $k$ 。
双指针法：可以利用双指针技巧来优化时间复杂度：
- 设定两个指针 $l$ 和 $r$ ，代表当前区间的左右边界。
- 初始时， $l = 1$ ， $r = 1$ ，然后我们通过移动右指针 $r$ 扩展区间，直到 $a_r - a_l > k$ 。
- 每次扩展区间后，计算当前区间的长度（即木板的数量），更新最大值。
- 当 $a_r - a_l > k$ 时，移动左指针 $l$ ，缩小区间，直到满足条件。

这种方法只需要遍历一次数组，所以时间复杂度为 $O (n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;const int N = 1e4 + 10;
int n, k, a[N];int main() {cin >> n >> k;for (int i = 1; i <= n; i++) {cin >> a[i];}int ans = 1;  // 至少能选一个木板for (int i = 1, j = 1; i <= n; i++) {while (j + 1 <= n && (a[j + 1] - a[i]) <= k) {j++;  // 扩展区间}ans = max(ans, j - i + 1);  // 更新最大木板数}cout << ans << endl;  // 输出结果return 0;
}