1481: 完善程序-2(最小区间覆盖)

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：253 Solved：28

Description

(最小区间覆盖) 给出n个区间，第i个区间的左右端点是[a b]。现在要在这些区间中选出若干个，使得区间[0 m] 被所选区间的并覆盖（即每一个0<=i<=m都在某个所选的区间中）。保证答案存在，球所选区间个数的最小值。

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

接下来n行，每行两个整数a[i]和b[i] ( 0<=a[i] b[i] <=b)。

提示： 使用贪心算法解决这个问题。先用O(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 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].a < A[j-1].a

C.     A[j].a > A[j-1].a

D.     A[j].b < A[j-1].b

(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[I-1].b

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

(4)    ④处应填(      )

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

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

C.     q<n && A[q].a <=r

D.     q<n && A[q].b <=r

(5)    ⑤处应填(      )

A.     r = max(r A[q+1].b)

B.     r = max(r A[q].b)

C.     r = max(r A[q+1].a)

D.     q++

Input

输入整数为题号。

Output

输出选项，大写字母。

Sample Input Copy

Sample Output Copy