#1916. 差异
差异
差异
题目描述
标题: 差异 - Problem - QOJ.ac
#10351. 差异
The problem was used in the following contests:
对于一个集合 S, 我们可以把其中所有元素从小往大排序, 我们定义这个集合的差异值为排好序后, 相邻两个数的差的最大值
你有 Q 个差异值不超过 K 非负整数集合, 已知每个集合中最小元素为 0, 最大元素为 N+1
现在已知给出 1 到 N 每个元素在 Q 个集合中的出现次数对M取模的结果, 求在满足条件的情况下, Q 的最小值是多少, 无解请输出 -1
输入描述
第一行三个整数 N, K, M 接下来一行 N 个整数, 第 i 个整数表示第 i 个元素的出现次数对 M 取模的结果
输出描述
一行一个整数表示 Q 的最小值, 无解输出 -1
样例输入1
3 2 8
0 0 1
样例输出1
8
样例输入2
3 1 9
2 3 3
样例输出2
-1
数据范围
对于10%的数据, K=1
对于另外10%的数据, K=2 且 N=5
对于另外20%的数据, K=2 且 N≤50
对于另外15%的数据, 保证答案小于M, 且N≤50
对于另外25%的数据, N≤20
对于100%的数据, 1≤N≤500000,1≤K≤N,2≤M≤109
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3 2 8
0 0 1
8
样例 2
3 1 9
2 3 3
-1