c++基础组（番桃）

Question

蟠桃
难度：
时间限制：1s
内存限制：256M
【题目描述】
在《西游记》的一个章节中，唐僧师徒四人在一片神秘的蟠桃园中进行采摘，准备为即将到来的斋戒仪式准备食物。蟠桃园中的蟠桃具有不同的灵气值，而唐僧的法力只能够允许他采摘一定范围内的灵气值的蟠桃。为了尽可能多地采摘蟠桃，他们决定采摘灵气值在一个连续区间内的蟠桃。孙悟空利用火眼金睛观察到每个蟠桃的灵气值，并告诉了唐僧。
唐僧需要在有
𝑛
n个蟠桃的蟠桃园中选择蟠桃，但他只能挑选那些灵气值落在一个长为
𝑚
m的连续区间内的蟠桃，也就是说唐僧从一个特定的灵气值
𝑥
x开始，只能选择灵气值大于等于
𝑥
x且小于
𝑥
+
𝑚
x+m的蟠桃。由于蟠桃园中的蟠桃数量众多，他们需要决定哪些蟠桃是应该采摘的，以便为仪式准备尽可能多的蟠桃。
现在唐僧想知道，他最多能采摘多少个蟠桃？
【输入格式】
第一行，两个正整数
𝑛
,
𝑚
n,m。分别表示蟠桃园中蟠桃的数量和唐僧采摘蟠桃的灵气值范围。
第二行，有
𝑛
n个正整数
𝑎
𝑖
a
i
​
，代表第
𝑖
i个蟠桃的灵气值。
【输出格式】
一个正整数，表示唐僧能采摘的最多的蟠桃数量。
【输入输出样例#1】
输入#1
10 6
2 4 6 7 10 11 12 12 18 20
复制
输出#1
5
复制
【说明提示】
样例#1解释：
有
10
10个蟠桃，灵气值分别为
2
,
4
,
6
,
7
,
10
,
11
,
12
,
12
,
18
,
20
2,4,6,7,10,11,12,12,18,20；唐僧可以选择的灵气值范围是连续的
6
6个数值。
从灵气值
2
2开始，可选蟠桃的灵气值范围是：
2
≤
2≤灵气值
＜
8
＜8，在这个范围内的蟠桃灵气值有：
2
,
4
,
6
,
7
2,4,6,7，共
4
4个。
从灵气值
4
4开始，可选蟠桃的灵气值范围是：
4
≤
4≤灵气值
＜
10
＜10，这个范围内的蟠桃灵气值有：
4
,
6
,
7
,
10
4,6,7,10，共
4
4个。
从灵气值
6
6开始，可选蟠桃的灵气值范围是：
6
≤
6≤灵气值
＜
12
＜12，在这个范围内的蟠桃灵气值有：
6
,
7
,
10
,
11
6,7,10,11，共
4
4个。
从灵气值
7
7开始，可选蟠桃的灵气值范围是：
7
≤
7≤灵气值
＜
13
＜13，在这个范围内的蟠桃灵气值有：
7
,
10
,
11
,
12
,
12
7,10,11,12,12，共
5
5个。
从灵气值
10
10开始，可选蟠桃的灵气值范围是：
10
≤
10≤灵气值
＜
16
＜16，在这个范围内的蟠桃灵气值有：
10
,
11
,
12
,
12
10,11,12,12，共
4
4个。
从灵气值
11
11开始，可选蟠桃的灵气值范围是：
11
≤
11≤灵气值
＜
17
＜17，在这个范围内的蟠桃灵气值有：
11
,
12
,
12
11,12,12，共
3
3个。
从灵气值
12
12开始，可选蟠桃的灵气值范围是：
12
≤
12≤灵气值
＜
18
＜18，在这个范围内的蟠桃灵气值有：
12
,
12
12,12，共
2
2个。
从灵气值
18
18开始，可选蟠桃的灵气值范围是：
18
≤
18≤灵气值
＜
24
＜24，在这个范围内的蟠桃灵气值有：
18
,
20
18,20，共
2
2个。
综上所述，从灵气值
7
7开始的区间可以得到最多的蟠桃数量，即
5
5个。
【数据范围】
1
≤
𝑁
≤
3
×
1
0
5
1≤N≤3×10
5

1
≤
𝑀
≤
1
0
9
1≤M≤10
9

1
≤
𝑎
𝑖
≤
1
0
9
1≤a
i
​
≤10
9

Answer 1

引自免费微信小程序：皆我百晓生

要解决这个问题，我们可以使用滑动窗口的方法。首先，我们需要遍历蟠桃的灵气值列表，然后维护一个窗口，窗口的大小就是给定的灵气值范围m。窗口内蟠桃的灵气值之和代表当前范围内蟠桃的总数。我们可以通过移动窗口来找到最大可能的蟠桃数。

以下是详细的C++代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    // 输入蟠桃数量和灵气值范围
    int n, m;
    std::cin >> n >> m;

    // 输入蟠桃的灵气值
    std::vector<int> peaches(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> peaches[i];
    }

    // 对灵气值排序
    std::sort(peaches.begin(), peaches.end());

    // 初始化滑动窗口的左侧边界和总和
    int left = 0, right = m - 1;
    int sum = 0;
    int max_peaches = 0;

    // 移动滑动窗口并更新最大蟠桃数
    while (right < n) {
        // 将右侧元素加入窗口并计算新窗口的总和
        sum += peaches[right];
        // 更新最大蟠桃数
        max_peaches = std::max(max_peaches, sum);

        // 将左侧元素移出窗口并减去其值
        sum -= peaches[left];
        // 移动窗口的左右边界
        left++;
        right++;
    }

    // 输出结果
    std::cout << max_peaches << std::endl;

    return 0;
}

这段代码首先读取输入，对蟠桃的灵气值进行排序，然后使用一个滑动窗口来计算不同灵气值范围内的蟠桃数。窗口的左侧边界left和右侧边界right随着循环的进行不断向右移动。每次移动后，都会计算新的窗口内蟠桃的总和，并与当前的最大蟠桃数进行比较，更新最大值。当窗口超出数组范围时，结束循环。最后输出最大的蟠桃数。

这个算法的时间复杂度是O(N log N)，其中N是蟠桃的数量。这是因为我们需要先对蟠桃的灵气值进行排序。空间复杂度是O(1)，因为我们只需要常数级别的额外空间来存储窗口的位置和当前的总和。