题库 信息学奥赛题库 题目列表 (最小区间覆盖)给出n个区间,第i个区间的左右端点是...
组合题

(最小区间覆盖)给出n个区间,第i个区间的左右端点是[ai, bi]。现在 要在这些区间中选出若干个,使得区间[0,m]被所选区间的并覆盖(即每 一个0≤i≤m都在某个所选的区间中)。保证答案存在,求所选区间个数 的最小值。

输入第一行包含两个整数n和m(1≤n≤5000, 1≤m≤10^9 )

接下来n行,每行两个整数ai,bi(0≤ai, bi ≤ m)。

提示:使用贪心法解决这个问题。先用0(n^2)的时间复杂度排序,然后贪心 选择这些区间。

试补全程序。

#include <iostream>
using namespace std;
const int MAXN = 5000;
int n, m;
struct segment { int a, b; } A[MAXN];
void sort() // 排序
{
    for (int i = 0; i < n; i++)
        for (int j = 1; j < n; j++)
            if (①)
            {
                segment t = A[j];
                ②
            }
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> A[i].a >> A[i].b;
    sort();
    int p = 1;
    for (int i = 1; i < n; i++)
        if (③)
            A[p++] = A[i];
    n = p;
    int ans = 0, r = 0;
    int q = 0;
    while (r < m)
    {
        while (④)
            q++;
        ⑤;
        ans++;
    }
    cout << ans << endl;
    return 0;
}
第1题 单选
①处应填()
A.
A[j].b<A[j-1].b
B.

A[j].b>A[j-1].b

C.

A[j].a<A[j-1].a

D.
A[j].a>A[j-1].a
第2题 单选

②处应填(   )

A.
A[j-1]=A[j];A[j]=t;
B.
A[j+1]=A[j];A[j]=t;
C.
A[j]=A[j-1];A[j-1]=t;
D.
A[j]=A[j+1];A[j+1]=t;
第3题 单选
③处应填(   )
A.
A[i].b<A[p-1].b
B.
A[i].b>A[i-1].b
C.

A[i].b>A[p-1].b

D.
A[i].b<A[i-1].b
第4题 单选
④处应填(   )
A.
q+1<n&&A[q+1].b<=r
B.
q+1<n&&A[q+1].a<=r
C.
q<n&&A[q].a<=r
D.
q<n&&A[q].b<=r
第5题 单选
⑤处应填()
A.
 r=max(r,A[q+1].a)
B.
r=max(r,A[q].b)
C.
r=max(r,A[q+1].b)
D.
q++
题目信息
完善程序 2020年 初赛
-
正确率
0
评论
148
点击