首页 > 代码库 > Cover

Cover

2024-09-04 03:48:55   218人阅读

【题目描述】

  有 N 个时间段，某个时间段可能包含其它时间段。

  请找出能包含其它时间段最多的那个段，并计算出它包括的其它时间段有多少？

 

【数据范围】

 1 <= N <= 25,000

 1 <= 时间段开始和结束点 <= 2,000,000,000

【输入格式】

 第1行：一个整数 N

 第2..N+1行：第i+1行有两个整数A，B(1 <= A < B <= 2,000,000,000)表示第 i 个时间段的开始和结束端点。任意两个时间段的端点不相同。

【输出格式】

 一行，一个整数。表示一段最多可包含的时间段数的最大值。

【样例输入】

4
1 7
2 3
5 6
4 10 

【样例输出】

2

 1 /*单调队列问题  按照左端点排一遍序 2 左端点简单入队 右端点分情况讨论  3 如果当前点Ti是右端点 并且与第一个时间点相匹配 4 则可以统计本段中的两端点都在期间的线段个数，并删除T1 5 删除T1之后如果T2的右端点已经出现过 T2可以继续删除 6 计数减一  因为他是T1-Ti的子段 不可能是最大解 7 不匹配时更加简单 计数+1  因为他一定是T1的子段  8 */ 9 #include<iostream>10 #include<cstdio>11 #include<cstring>12 #include<algorithm>13 using namespace std;14 struct self {15     int x,y;16     bool operator < (const self &a) const{17         return x<a.x;18     }19 }s[25555];20 int t[25555],q[25555],head,tail,ans,n;21 void work(){22     head=tail=1;23     q[head]=1;24     for(int i=2;i<=n;i++) {25         bool update=0;26         while(s[q[head]].y<s[i].x&&head<=tail)head++;27         for(int j=tail;j>=head;j--)28             if(s[q[j]].y>s[i].y) {29                 update=1;30                 t[q[j]]++;31                 ans=max(ans,t[q[j]]);32             }33         if(!update){34             tail++;35             q[tail]=i;36         }37     }38 }39 int main(){40     scanf("%d",&n);41     for(int i=1;i<=n;i++)42         scanf("%d%d",&s[i].x,&s[i].y);43     sort(s+1,s+n+1);44     work();45     cout<<ans<<endl;46     return 0;47 }

 

Cover


联系
我们