单选题
适中
#24784
下面程序的运行结果为( )。 bool check(int n, int a[], int k, int dist) { int cnt = 1; int la…
下面程序的运行结果为( )。
bool check(int n, int a[], int k, int dist) {
int cnt = 1;
int last = a[0];
for (int i = 1; i < n; i++) {
if (a[i] - last >= dist) {
cnt++;
last = a[i];
}
}
return cnt >= k;
}
int solve(int n, int a[], int k) {
std::sort(a, a + n);
int l = 0;
int r = a[n - 1] - a[0];
while (l < r) {
int mid = (l + r + 1) / 2;
if (check(n, a, k, mid))
l = mid;
else
r = mid - 1;
}
return l;
}
int main() {
int a[] = {1, 2, 8, 4, 9};
int n = 5;
int k = 3;
std::cout << solve(n, a, k) << std::endl;
return 0;
}
答案与解析
正确答案:B
解析
函数check用于判断在给定距离dist下,数组a中最多能选出多少个元素满足相邻元素间距离不小于dist。通过贪心策略遍历已排序的数组,统计满足条件的元素个数cnt,并与k比较。函数solve对数组a进行排序,确定答案的二分查找范围为[0, a[n-1]-a[0]]。在二分过程中,根据check返回值调整边界,寻找最大可行的dist值。整个过程基于二分答案与贪心验证的结合,逐步缩小搜索空间直至收敛到最终结果。