#cspjc2020w2. 2020csp-j初赛完善程序2

2020csp-j初赛完善程序2

2020csp-j初赛完善程序2

每小题3 分

1.第二题

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

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

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

​ 提示:使用贪心法解决这个问题。先用 O(n2)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 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.①处应填( ){{ select(1) }}

  • A[j].b>A[j-1].b
  • A[j].a<A[j-1].a
  • A[j].a>A[j-1].a
  • A[j].b<A[j-1].b

2.②处应填( ){{ select(2) }}

  • A[j+1]=A[j];A[j]=t;
  • A[j-1]=A[j];A[j]=t;
  • A[j]=A[j+1];A[j+1]=t;
  • A[j]=A[j-1];A[j-1]=t;

3.③处应填( ) {{ select(3) }}

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

4.④处应填( ) {{ select(4) }}

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

5.⑤处应填( ) {{ select(5) }}

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