组合题

(最小区间覆盖)给出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 - l].b

C

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

D

A[i].b < A[i - 1].b

第4题 单选题

④处应填()

A

q + 1 < n && A[q + l].b <= r

B

q + 1 < n && A[q + l].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++

赣ICP备20007335号-2