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

AT_abc403_d.[ABC403D] Forbidden Difference

普及+/提高

通过率：0%

AC君温馨提醒

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

题目描述

给定一个长度为 NN 的整数序列 A=(A1,A2,…,AN)A=(A_1,A_2,\dots,A_N) 和一个非负整数 DD。我们需要通过删除 AA 中的若干元素，得到一个新序列 BB，使其满足以下条件：

  • 对于所有 i,j  (1≤i<j≤∣B∣)i,j\ \ (1 \leq i < j \leq |B|)，都有 ∣Bi−Bj∣≠D|B_i - B_j| \neq D。

求最少需要删除多少个元素才能满足条件。

输入格式

输入通过标准输入给出，格式如下：

NN DD
A1A_1 A2A_2 …\dots ANA_N

输出格式

输出需要删除的最少元素数量。

输入输出样例

  • 输入#1

    5 2
3 1 4 1 5

    输出#1

    1

  • 输入#2

    4 3
1 6 1 8

    输出#2

    0

  • 输入#3

    10 3
1 6 2 10 2 3 2 10 6 4

    输出#3

    2

说明/提示

约束条件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 0≤D≤1060 \leq D \leq 10^6
  • 0≤Ai≤1060 \leq A_i \leq 10^6
  • 输入中的所有值均为整数

样例解释 #1

删除 A1=3A_1=3，得到 B=(1,4,1,5)B=(1,4,1,5)，此时对于所有 i<ji<j，都有 ∣Bi−Bj∣≠2|B_i - B_j| \neq 2。

样例解释 #2

原始序列 AA 已经满足条件，因此不需要删除任何元素。

翻译由 DeepSeek V3 完成

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

首页