问题标题: 酷町堂：4369 布展（diff)

Question

0

已解决

卞福睿

中级守护

4369 布展（diff)

经验值：1600 时间限制：1000毫秒

庐阳区2019年**学竞赛试题

不许抄袭，一旦发现，直接清空经验！

题目描述 Description

有N颗大小不一的钻石，现在需要布展，为了视觉效果，你可以去掉其中最多K颗钻石，使得展台上的最大的钻石与最小的钻石差值最小。求解这个最小值。

输入描述 Input Description

第一行两个整数N和K。
接下来N个整数Ai，表示钻石的大小。

输出描述 Output Description

一个整数，意义如题所述。

样例输入 Sample Input

3 1 1 2 4

样例输出 Sample Output

1

数据范围及提示 Data Size & Hint

数据范围
1＜＝N＜＝100000
1＜＝Ai＜＝100000
0＜＝K＜N

请问怎么做（可提供具体思路和部分代码），谢谢！

酷町豆刷题求解 C++ 0条评论 3 年，1 月前

Answer 1

已采纳

汪恺恒

中级启示者

滑动窗口

先对数组从小到大排序，然后枚举找最小值

int i=1,j=n-m;
    while(j<=n){
        ans=min(ans,a[j]-a[i]);
        i++,j++;
    }