给出n个区间,第i个区间的左右端点是[,],现在要在这些区间中选出若干个,使得区间[0,m]被所选区间的并覆盖(即每一个0<=i<=m都在某个所选的区间中)。保证答案存在,求所选区间个数的最小值。
输入第一行包含两个整数n和m (1<=n<=5000,1<=m<=10^9)
接下来n行,每行两个整数, (0<=,<=m)。
提示:使用贪心法解决这个问题。先用o(n^2)的时间复杂度排序,然后贪心选择这些区间。
试补全程序。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #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 (__1__){ segment t=A[j]; __2__ } } 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 = 0; i < n; i++) if(__3__) A[p++]=A[i]; n=p; int ans=0,r=0; int q=0; while(r<m){ while(__4__) q++; __5__; ans++; } cout<<ans<<endl; return 0; } |
0 of 5 Questions completed
Questions:
You have already completed the quiz before. Hence you can not start it again.
Quiz is loading…
You must sign in or sign up to start the quiz.
You must first complete the following:
0 of 5 Questions answered correctly
Your time:
Time has elapsed
You have reached 0 of 0 point(s), (0)
Earned Point(s): 0 of 0, (0)
0 Essay(s) Pending (Possible Point(s): 0)
__1__处应填( )
__2__处应填( )
__3__处应填( )
__4__处应填( )
__5__处应填( )