ABC361 C题解

xuyunao · 2024-07-07 07:31:00 · 题解

ABC361 C题解

原题 题目要求删除几个元素后使数组的极差最小

那么怎么样求最小的极差呢？

众所周知，极差 = 最大值 - 最小值

因此想要使极差最小，就要尽可能的增加最小值或减少最大值；因此删除的K个数要从有序数组中删除头尾，并查找出极差最小情况

首先我们需要输入这个数组并对他进行排序

bool cmp(int a,int b)
{
    return a < b;
}

int n,k;
cin >> n >> k;
for(int i = 0;i < n;i++)
{
    cin >> a[i];
}
sort(a,a+n,cmp);

然后枚举K种情况：

• 设开头删除i个数，则剩余极差=a[i + n - k - 1] - a[i]
• 接下来求取最小值即可