二分查找 - 阅读程序（一）

题目描述

阅读以下程序，回答判断题（第 1-3 题，每题 15 分）和选择题（第 4-6 题，第 4-5 题各 15 分，第 6 题 25 分）。

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10;
int n, s, cnt, ans, res;
int a[N], b[N];

bool check(int mid) {
     for (int i = 1; i <= n; i++)
         b[i] = a[i] + i * mid;
     sort(b + 1, b + 1 + n);
     res = 0;
     for (int i = 1; i <= mid && res <= s; i++)
         res += b[i];
     return res <= s;
}

int main() {
     scanf("%d%d", &n, &s);
     for (int i = 1; i <= n; i++)
         scanf("%d", &a[i]);
     int l = 0, r = n;
     while (l <= r) {
         int mid = (l + r) >> 1;
         if (check(mid)) cnt = mid, ans = res, l = mid + 1;
         else r = mid - 1;
     }
     printf("%d %d\n", cnt, ans);
     return 0;
}

判断题

第 1 题 若输入 4 100 1 2 5 6，则程序的输出为 4 54。{{ select(1) }}

• 正确
• 错误

第 2 题 对于任意的输入，cnt 的一个必定合法的取值为 n。{{ select(2) }}

• 正确
• 错误

第 3 题 这个程序的时间复杂度为 O(n log n)。{{ select(3) }}

• 正确
• 错误

选择题

第 4 题 当输入为 3 11 2 3 5 时，程序的输出为（ ）。{{ select(4) }}

• A. 1 11
• B. 2 11
• C. 3 8
• D. 0 0

第 5 题 代码中 check 函数的作用是什么？（ ）{{ select(5) }}

• A. 判断当前数组是否有序
• B. 检查是否能从数组中选出 mid 个数，使得它们的总和小于或等于 s
• C. 判断数组的所有元素是否大于某个值
• D. 计算数组元素的平均值

第 6 题（25 分） 变量 cnt 和 ans 的作用分别是什么？（ ）{{ select(6) }}

• A. cnt 记录满足条件的最大 mid 值，ans 记录对应的总和
• B. cnt 记录数组的长度，ans 记录数组中的最大值
• C. cnt 表示排序后的最小值索引，ans 记录当前结果的最小值
• D. cnt 表示满足条件的元素个数，ans 记录最终的目标值