Thứ Bảy, 14 tháng 11, 2020

In ra số tập tối thiểu cần để phủ đoạn [0;M]

 Đề bài: $\href{https://acm.timus.ru/problem.aspx?space=1&num=1303}{Đây}$

Tóm tắt: Cho một tập segment , và số M. Nhiệm vụ: In ra số tập tối thiểu cần dùng để phủ đoạn trên.

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. int m,p,a,b;
  4. struct xd{
  5. int s,e;
  6. bool operator < (const xd& a)const{
  7. return s<a.s;
  8. }
  9. }ss[100005];
  10. int vis[100005];
  11. int main(){
  12. p=0;
  13. memset(vis,0,sizeof vis);
  14. scanf("%d",&m);
  15. while(scanf("%d%d",&a,&b)){
  16. if(a==0&&b==0)break;
  17. if(b<=0||a>=m||a==b)continue;
  18. ss[p].s=a,ss[p].e=b;
  19. p++;
  20. }
  21. sort(ss,ss+p);
  22. int flag=1,ed=0,pos=0,tp=0;
  23. while(ed<m){
  24. int ned=0,ni=0;
  25. while(pos<p&&ss[pos].s<=ed){
  26. if(ss[pos].e>ned){
  27. ned=ss[pos].e;
  28. ni=pos;
  29. }
  30. pos++;
  31. }
  32. if(ned==0){flag=0;break;}
  33. ed=ned;
  34. vis[ni]=1;
  35. tp++;
  36. }
  37. if(p==0||flag==0){
  38. printf("No solution\n");
  39. }else{
  40. printf("%d\n",tp);
  41. for(int i=0;i<p;i++){
  42. if(vis[i])printf("%d %d\n",ss[i].s,ss[i].e);
  43. }
  44. }
  45. return 0;
  46. }

Không có nhận xét nào:

Đăng nhận xét

Cho mảng A gồm n phần tử, sắp xếp lại mảng này sao cho số cặp a[i] bé hơn a[i+1] lớn nhất có thể

 Đề bài: $\href{https://codeforces.com/problemset/problem/651/B}{Đây}$  Tóm tắt:Cho một mảng gồm n phần tử, hãy sắp xếp lại mảng theo thứ tự...