c语言贪心算法数列极差问题
时间: 2023-11-20 20:35:58 浏览: 58
题目描述:
给定一个长度为N的数列,要求从中选出K个数,使得这K个数的最大值与最小值的差最小,输出这个最小的差值。
贪心算法思路:
首先,我们考虑最优解的性质。如果我们已经找到了一个最优解,那么这个最优解中最大值和最小值肯定是原数列中的某两个数。因此,我们可以将数列中的所有数按照大小排序,然后枚举所有可能的最大值和最小值,计算每种情况下的差值,最后取最小值即可。
C语言代码实现:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 1000
int a[MAXN];
int n, k;
int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
qsort(a, n, sizeof(int), cmp);
int ans = a[n - 1] - a[0];
for (int i = 0; i <= n - k; ++i) {
int j = i + k - 1;
if (j < n) {
int d = a[j] - a[i];
if (d < ans) {
ans = d;
}
}
}
printf("%d\n", ans);
return 0;
}