95分超时求调orz
查看原帖
95分超时求调orz
1098096
aoding_buxiangxuele楼主2024/8/29 17:41

按第一个题解的思路自己写的,第19个点和补的3个点超时了

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+5;
int n,m1,m2,ans;
struct node{
	int x,y;//抵达时间 离开时间
};
node d1[N],d2[N]; 
bool cmp(node a,node b){
	return a.x<b.x;//先到先得 
}
struct lq{
	int f,n;//廊桥状态 累计数量 
};
lq a[N],b[N];
struct tk{
	int lq,y;//廊桥编号 离开时间 
}; 
struct tkcmp{
	bool operator()(const tk& a,const tk& b){
		return a.y>b.y;
	}
};

int main(){
	scanf("%d%d%d",&n,&m1,&m2);//获取廊桥总数和国内区航班数和国际区航班数 
	for(int i=1;i<=m1;i++) scanf("%d%d",&d1[i].x,&d1[i].y);//获取国内区航班抵达离开时间 
	for(int i=1;i<=m2;i++) scanf("%d%d",&d2[i].x,&d2[i].y);//同上 
	sort(d1+1,d1+1+m1,cmp);//按抵达时间排序 
	sort(d2+1,d2+1+m2,cmp);
	
	//假设廊桥数量无限多 到达的飞机占用编号最小的空闲廊桥 并统计每个廊桥停过多少航班
	//那么廊桥1~n能停的航班总数就是n个廊桥能停的总数 
	
	//按离开时间升序排列停机情况
	priority_queue<tk,vector<tk>,tkcmp> q1,q2;
	
	for(int i=1;i<=m1;i++){//遍历国内区航班 记录每个廊桥能停靠多少个航班 
		if(q1.empty()){
			q1.push({1,d1[i].y});//进入停靠队列 
			a[1].f=1;//廊桥状态变为繁忙 
			a[1].n++;//分配廊桥 对应廊桥累计停靠数量增加 
		}else{
			while(!q1.empty()&&d1[i].x>q1.top().y){//将飞机离开的廊桥变为空闲 
				a[q1.top().lq].f=0;
				q1.pop();
			}
			for(int j=1;j<=m1;j++) if(a[j].f==0){
				a[j].f=1;
				q1.push({j,d1[i].y});
				a[j].n++;
				break; 
			}
		}
	}
	for(int i=1;i<=m2;i++){//遍历国际区航班 
		if(q2.empty()){
			q2.push({1,d2[i].y});//进入停靠队列 
			b[1].f=1;//廊桥状态变为繁忙 
			b[1].n++;//分配廊桥 对应廊桥累计停靠数量增加 
		}else{
			while(!q2.empty()&&d2[i].x>q2.top().y){
				b[q2.top().lq].f=0;
				q2.pop();
			}
			for(int j=1;j<=m2;j++) if(b[j].f==0){
				b[j].f=1;
				q2.push({j,d2[i].y});
				b[j].n++;
				break;
			}
		}
	}
	
	for(int i=1;i<=n;i++){//每个廊桥可停靠航班数做成前缀和 即是对应数量廊桥可停靠航班数 
		a[i].n+=a[i-1].n;
		b[i].n+=b[i-1].n;
	}
	for(int i=0;i<=n;i++) ans=max(ans,a[i].n+b[n-i].n);
	printf("%d",ans);
	return 0;
}
2024/8/29 17:41
加载中...