题目名称 2988. 简单题kewu
输入输出 kewu.in/out
难度等级 ★★★
时间限制 2000 ms (2 s)
内存限制 512 MB
测试数据 5 简单对比
题目来源 2018-10-07
开放分组 全部用户
提交状态
分类标签
hs的简单题
通过:8, 提交:67, 通过率:11.94%
GravatarPorsche 100 0.161 s C++
Gravatarxudaxia 100 0.204 s C++
GravatarPotremZ 100 0.207 s C++
Gravatarxudaxia 100 0.213 s C++
GravatarPotremZ 100 0.218 s C++
GravatarPotremZ 100 0.219 s C++
GravatarPorsche 100 0.222 s C++
GravatarHorrigue_JyowYan 100 0.369 s C++
GravatarAkoasm 100 3.297 s C++
Gravatar梦那边的美好ETMN 100 3.395 s C++
关于 简单题kewu 的讨论
写了个假算法,居然过了233(稍微放大了一点点时限)
Gravatarluo
2018-10-09 23:06 1楼
想到了应该是正解的东西,最坏O(n^2+mlogm),时限降到2s
Gravatarluo
2018-10-10 12:45 2楼

2988. 简单题kewu

★★★   输入文件:kewu.in   输出文件:kewu.out   简单对比
时间限制:2 s   内存限制:512 MB

【题目描述】


小滑稽们太可恶了,大滑稽决定给他们点颜色看看。

总共有n个小滑稽,第i个小滑稽有一个滑稽值ai,没有两个滑稽的滑稽值相同。大滑稽想找到一个尽量小的滑稽上限m,并干掉最多k个小滑稽,使得剩下的小滑稽们的滑稽值除以m的余数互不相同。

请问m最小是多少呢?


【输入格式】


第一行两个整数n和k。

接下来n行每行一个整数表示程度值ai。


【输出格式】


一行一个整数表示最小的m。


【样例输入】

5 1
1
2
10
11
12

【样例输出】

4

【提示】


对于20%的数据n<=10;

对于100%的数据0<=k<=4,n<=5000,1<=ai<=1000000。