#cspjc2020w2. 2020csp-j初赛完善程序2
2020csp-j初赛完善程序2
2020csp-j初赛完善程序2
每小题3 分
1.第二题
(最小区间覆盖) 给出 n个区间,第 i个区间的左右端点是 。现在要在这些区间中选出若干个,使得区间 [0,m]被所选区间的并覆盖(即每一个 0≤i≤m 都在某个所选的区间中)。保证答案存在,求所选区间个数的最小值。
输入第一行包含两个整数 n 和 m
接下来 n行,每行两个整数 。
提示:使用贪心法解决这个问题。先用 的时间复杂度排序,然后贪心选择这些区间。
试补全程序。
#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++