For hlep
查看原帖
For hlep
934977
lichengxi1楼主2024/8/21 22:44

我的做法是:

用in,out来记录当前最早离开的飞机的离开时刻和所在廊桥

用q来记录目前编号最小的空余廊桥

用vis来记录当前廊桥是否被占用

代码:

#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1e5 + 10;
int n,m1,m2,x[MAXN],y[MAXN];
bool vis[MAXN];
struct Time{
	int s,t;
}a[MAXN],b[MAXN];
struct Node{
	int t,id;
	bool operator<(const Node &a)const{return this->t > a.t;}
};

bool cmp(Time x,Time y){return x.s < y.s;}

void calc1(){
	memset(vis,0,sizeof(vis));
	priority_queue<Node> in;
	priority_queue<int,vector<int>,greater<int> > q;
	for(int i = 1;i <= n;++i){
		q.push(i);
		vis[i] = 1;
	}
	for(int i = 1;i <= m1;++i){
		while(!in.empty() && a[i].s > in.top().t){
			if(!vis[in.top().id]){
				q.push(in.top().id);
				vis[in.top().id] = 1;
			}
			in.pop();
		}
		if(q.size()){
			in.push({a[i].t,q.top()});
			x[q.top()]++;
			vis[q.top()] = 0;
			q.pop();
			continue;
		}
	}
	for(int i = 1;i <= n;++i) x[i] += x[i - 1];
	return ;
}

void calc2(){
	memset(vis,0,sizeof(vis));
	priority_queue<Node> out;
	priority_queue<int,vector<int>,greater<int> > q;
	for(int i = 1;i <= n;++i) q.push(i);
	for(int i = 1;i <= m2;++i){
		while(!out.empty() && b[i].s > out.top().t){
		    if(!vis[out.top().id]){
		    	q.push(out.top().id);
		    	vis[out.top().id] = 1;
		    }
			out.pop();
		}
		if(q.size()){
			out.push({b[i].t,q.top()});
			y[q.top()]++;
			vis[q.top()] = 0;
			q.pop();
		}
	}
	for(int i = 1;i <= n;++i) y[i] += y[i - 1];
	return ;
}

int main(){
	ios::sync_with_stdio(false);
	cin >> n >> m1 >> m2;
	for(int i = 1;i <= m1;++i) cin >> a[i].s >> a[i].t;
	for(int i = 1;i <= m2;++i) cin >> b[i].s >> b[i].t;
	sort(a + 1,a + m1 + 1,cmp);
	sort(b + 1,b + m2 + 1,cmp);
	calc1();
	calc2();
	int ans = -1e9;
	for(int i = 1;i <= n;++i) ans = max(ans,x[i] + y[n - i]);
	cout << ans << endl;
	return 0;
}

95分,第一个点WA,其他全对

麻烦大佬们帮忙调一下,万分感谢

2024/8/21 22:44
加载中...