Thứ Sáu, 13 tháng 11, 2020

Bài toán tìm số đoạn lớn nhất đi qua ít nhất một điểm trên mặt phẳng

 Đề bài: $\href{https://zoj.pintia.cn/problem-sets/91827364500/problems/91827370515}{Đây}$

Tóm tắt: Cho n đoạn thẳng trong mặt phẳng 2 chiều, có tọa độ lần lượt là $(l_i,i),(r_i,i)\forall 1\le i\le n$. Trên mặt phẳng này, tại mỗi điểm nguyên , ta có thể gắn một thẻ bài trên đó, sao cho hoành độ của tất cả các lá bài được gán khác nhau từng đôi một. 

Yêu cầu: In ra số lượng đoạn thẳng lớn nhất thỏa mãn, mỗi đoạn thẳng đi qua ít nhất một thẻ bài

Source:

  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. struct Segment{
  4. int l,r;
  5. bool operator<(Segment a) const{
  6. if(l==a.l)
  7. return r>a.r;
  8. return l>a.l;
  9. }
  10. };
  11. priority_queue<Segment> q;
  12. int main(){
  13. int T,n,ans,x,y;
  14. scanf("%d",&T);
  15. while(T--){
  16. ans=0;
  17. while(!q.empty()) q.pop();
  18. scanf("%d",&n);
  19. while(n--){
  20. Segment t;
  21. scanf("%d%d",&x,&y);
  22. t.l=x;
  23. t.r=y;
  24. q.push(t);
  25. }
  26. int k=0;
  27. while(!q.empty()){
  28. Segment u = q.top();
  29. q.pop();
  30. if(u.l==k){
  31. u.l++;
  32. if(u.l<=u.r) q.push(u);
  33. }
  34. else{
  35. k=u.l;
  36. ans++;
  37. }
  38. }
  39. printf("%d\n",ans);
  40. }
  41. return 0;
  42. }

 

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ự...