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

题目描述

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

已知 k ≤ n × m，保证 n、m 同阶。

#include<bits/stdc++.h>
using namespace std;
int n, m, k, l, r, mid;
int check(int g) {
    int st = 1, ed = m, cnt = 0;
    while(st <= n && ed >= 1) {
        if(st * ed > g)
            ed--;
        else {
            cnt += ed;
            st++;
        }
    }
    return cnt >= k;
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    l = 1, r = n * m;
    while(l < r) {
        mid = (l + r) / 2;
        if(check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
    return 0;
}

判断题

第 1 题 每次运行 check 时，第 7 行必定运行 n 次。{{ select(1) }}

• 正确
• 错误

第 2 题 如果保证 m = 1，则输出一定为 k。{{ select(2) }}

• 正确
• 错误

第 3 题 若将第 21 行中的 r = mid 改成 r = mid - 1，程序输出一定不变。{{ select(3) }}

• 正确
• 错误

第 4 题 第 24 行可以改成 cout << r << endl;。{{ select(4) }}

• 正确
• 错误

选择题

第 5 题 该程序的时间复杂度为（ ）{{ select(5) }}

• A. O(n)
• B. O(n log n)
• C. O(n²)
• D. O(nk)

第 6 题 若输入为 2 3 4，则输出为（ ）{{ select(6) }}

• A. 1
• B. 2
• C. 3
• D. 6