题目名称 2988. 简单题kewu
输入输出 kewu.in/out
难度等级 ★★★
时间限制 2000 ms (2 s)
内存限制 512 MB
测试数据 5 简单对比
题目来源 2018-10-07
开放分组 全部用户
提交状态
分类标签
hs的简单题
通过:2, 提交:30, 通过率:6.67%
Gravatar梦那边的美好ETMN 100 3.395 s C++
Gravatarluo 100 3.426 s C++
Gravatarluo 100 3.426 s C++
Gravatarluo 40 3.478 s C++
Gravatarluo 40 3.518 s C++
Gravatark423 40 3.684 s C++
Gravatark423 40 3.723 s C++
Gravatarluo 40 3.764 s C++
Gravatarluo 40 3.794 s C++
Gravatarluo 40 4.615 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。