题目详情题解（0）讨论（0）提交记录（0）

AT_abc326_c.[ABC326C] Peak

普及-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

高桥君在数轴上放置了 NN 个礼物。其中，第 ii 个礼物被放在坐标 AiA_i 上。

你可以选择数轴上的一个长度为 MM 的半开区间 [x,x+M)[x, x+M)，并获得所有落在该区间内的礼物。
具体来说，获得礼物的步骤如下：

  • 首先，选择一个实数 xx。
  • 然后，获得所有满足 x≤Ai<x+Mx \leq A_i < x+M 的礼物。

你最多能获得多少个礼物？

输入格式

输入以如下格式从标准输入给出。

NN MM A1A_1 A2A_2 …\dots ANA_N

输出格式

请输出你最多能获得的礼物数量，作为一个整数。

输入输出样例

  • 输入#1

    8 6
2 3 5 7 11 13 17 19

    输出#1

    4

  • 输入#2

    10 1
3 1 4 1 5 9 2 6 5 3

    输出#2

    2

  • 输入#3

    10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853

    输出#3

    7

说明/提示

限制条件

  • 所有输入均为整数。
  • 1≤N≤3×1051 \leq N \leq 3 \times 10^5
  • 1≤M≤1091 \leq M \leq 10^9
  • 0≤Ai≤1090 \leq A_i \leq 10^9

样例解释 1

例如，指定半开区间 [1.5,7.5)[1.5, 7.5) 时，坐标为 2,3,5,72, 3, 5, 7 的 44 个礼物都可以获得，这是可以获得的最大数量。

样例解释 2

同一个坐标上也可能放有多个礼物。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页