题目类型

CSP-J 初赛风格完善程序题。本题所有空均已改为单项选择，不需要手动输入代码。每空只有一个正确选项。

程序说明

输入 n 条记录，每条记录包含三个正整数 l、r、w，其中 l <= r。程序会对记录重新排序、筛选并输出一个值。筛选规则和输出值的实际意义没有直接给出，需要结合排序、二分查找和 dp 状态自行推断。

可以把每条记录看成占用闭区间 [l,r] 并带有权值 w。数据保证 1 <= n <= 100000。

程序

#include <bits/stdc++.h>
using namespace std;

const int N = 100005;

struct Node {
    int l, r;
    long long w;
} a[N];

int n;
long long dp[N];

bool cmp(Node x, Node y) {
    if (x.r != y.r)
        return /* 空 1 */;
    return x.l < y.l;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i].l >> a[i].r >> a[i].w;

    sort(a + 1, a + n + 1, cmp);
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        int left = 1, right = i - 1;
        int pos = 0;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (/* 空 2 */) {
                /* 空 3 */;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        dp[i] = /* 空 4 */;
    }

    cout << /* 空 5 */ << '\n';
    return 0;
}

选择区

空 1（20 分）

为了使后续二分查找成立，记录应首先按右端点从小到大排序。空 1 应填（　）。

{{ select(1) }}

• A. x.l < y.l
• B. x.r < y.r
• C. x.w > y.w
• D. x.r > y.r

空 2（20 分）

程序要寻找排在 i 前面、且与第 i 条记录的闭区间没有公共位置的最靠后记录。空 2 应填（　）。

{{ select(2) }}

• A. a[mid].r <= a[i].r
• B. a[mid].l < a[i].l
• C. a[mid].r < a[i].l
• D. a[mid].l > a[i].r

空 3（20 分）

当 mid 对应的记录满足条件时，需要保存当前候选位置。空 3 应填（　）。

{{ select(3) }}

• A. pos = left
• B. pos = right
• C. pos = i
• D. pos = mid

空 4（20 分）

dp[i] 表示只考虑排序后前 i 条记录时程序能得到的最优值。空 4 应填（　）。

{{ select(4) }}

• A. max(dp[i - 1], dp[pos] + a[i].w)
• B. min(dp[i - 1], dp[pos] + a[i].w)
• C. dp[i - 1] + a[i].w
• D. max(dp[pos], a[i].w)

空 5（20 分）

程序最终应输出（　）。

{{ select(5) }}

• A. dp[0]
• B. dp[n]
• C. dp[n - 1]
• D. a[n].w