33OJ
登录 注册

#P17756. 「RSOI-3E」集合构造 / set

「RSOI-3E」集合构造 / set

背景

题目来源:【HT-126-Div.2】核桃 CSP-S 组模拟赛

题目描述

给定一个长度为 nn 的正整数序列 A={A1,A2,…,An}A = \{A_1, A_2, \dots, A_n\},以及非负整数 kk 和正整数 dd。

你可以构造一个正整数多重集合 BB,要求满足 ∣B∣≤k|B| \le k(即集合 BB 中最多包含 kk 个元素,且元素可以任意指定)。

令集合 S=A∪BS = A \cup B。你需要从 SS 中选出一个子集 T⊆ST \subseteq S,使得 TT 中的元素在按严格递增顺序排列后 t1<t2<⋯<tmt_1 < t_2 < \dots < t_m,能够满足:

  • 对于任意 1≤i<m1 \le i < m,均有 ti+1−ti≤dt_{i+1} - t_i \le d。

求 ∣T∣|T| 的最大值(即 mm 的最大值)。

输入格式

输入共两行。

第一行,三个整数 n,k,dn, k, d。

第二行,包含 nn 个正整数表示序列 AiA_i。

输出格式

输出共一行,一个整数表示 ∣T∣|T| 的最大值。

5 1 2
1 4 8 9 13
4
8 2 3
10 15 2 4 16 11 5 20
9

提示

【样例解释 #1】

对于样例 #1,原序列 AA 去重并排序后为 {1,4,8,9,13}\{1, 4, 8, 9, 13\}。

我们可以选择 AA 中的子集 {4,8,9}\{4, 8, 9\},并构造集合 B={6}B = \{6\}(只使用了 11 个元素,满足 ∣B∣≤1|B| \le 1)。

此时 T={4,6,8,9}T = \{4, 6, 8, 9\},排序后相邻两项的差值分别为 2,2,12, 2, 1,均不超过 d=2d=2。集合 TT 的大小为 44。

【样例解释 #2】

对于样例 #2,原序列 AA 去重排序后为 {2,4,5,10,11,15,16,20}\{2, 4, 5, 10, 11, 15, 16, 20\}。

选取 AA 中的 {2,4,5,10,11,15,16}\{2, 4, 5, 10, 11, 15, 16\},并令 B={8,14}B = \{8, 14\}。

此时 T={2,4,5,8,10,11,14,15,16}T = \{2, 4, 5, 8, 10, 11, 14, 15, 16\},相邻差值最大为 33,大小为 99。

【数据范围】

本题采用捆绑测试。

对于所有测试数据,保证: 1≤n≤1051 \le n \le 10^5,0≤k≤1090 \le k \le 10^9,1≤d,Ai≤1091 \le d, A_i \le 10^9。

子任务编号 n≤n\le 特殊性质 分值
1 10210^2 k=0k=0 1515
2 10310^3 无
3 10510^5 k=0k=0 2020
4 d=1d=1
5 无 3030