Đề 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:
- #include<bits/stdc++.h>
- using namespace std;
- struct Segment{
- int l,r;
- bool operator<(Segment a) const{
- if(l==a.l)
- return r>a.r;
- return l>a.l;
- }
- };
- priority_queue<Segment> q;
- int main(){
- int T,n,ans,x,y;
- scanf("%d",&T);
- while(T--){
- ans=0;
- while(!q.empty()) q.pop();
- scanf("%d",&n);
- while(n--){
- Segment t;
- scanf("%d%d",&x,&y);
- t.l=x;
- t.r=y;
- q.push(t);
- }
- int k=0;
- while(!q.empty()){
- Segment u = q.top();
- q.pop();
- if(u.l==k){
- u.l++;
- if(u.l<=u.r) q.push(u);
- }
- else{
- k=u.l;
- ans++;
- }
- }
- printf("%d\n",ans);
- }
- return 0;
- }
Không có nhận xét nào:
Đăng nhận xét