30分求助
查看原帖
30分求助
1054226
Tsang724560楼主2023/10/9 17:54

1 2 4 9 15 16 21 22过了,其他全WA

题目给的第3个样例过不了

大佬帮帮吧

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<utility>
#include<queue>
using namespace std;

int n,ans;//n个廊桥,答案 
int inFlight,outFlight,inBridge,outBridge;//航班数,分配廊桥数 
int inNeed[100003],outNeed[100003];//记录每个航班对应廊桥,也许用得到 
int inSum[100003],outSum[100003];//记录第1...i个廊桥服务的航班数量 
struct Time{
	int arrive,leave;
}inTime[100003],outTime[100003];//航班信息 
priority_queue< pair<int,int> > q;
//名字in开头的变量是关于国内航班的,out开头是国际航班 

bool cmp(Time x,Time y){
	return x.arrive<y.arrive;
}//sort的比较函数:来得早的航班排在前面 

int Read(){
	int x=0;char c;
	c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9'){
		x=(x<<3)+(x<<1)+int(c)-48;
		c=getchar();
	}
	return x;
}//快读 

void Push1(int i,int x){
	q.push(make_pair(-inTime[i].leave,x));
	return;
}//国内航班入队 

void Push2(int i,int x){
	q.push(make_pair(-outTime[i].leave,x));
	return;
}//国际航班入队 

int main()
{
//	freopen("airport3.in","r",stdin);
//	freopen("airport.out","w",stdout);
	n=Read();inFlight=Read();outFlight=Read();
   //输入数据,按到达时间排序 
	for(int i=1;i<=inFlight;i++){
		inTime[i].arrive=Read();
		inTime[i].leave=Read();
	}
	sort(inTime+1,inTime+1+inFlight,cmp);
	for(int i=1;i<=outFlight;i++){
		outTime[i].arrive=Read();
		outTime[i].leave=Read();
	}
	sort(outTime+1,outTime+1+outFlight,cmp);
	
   //分配廊桥:优先队列q用来寻找最先起飞的航班,
   //inSum[i]或outSum[i]用来统计第i个廊桥服务多少航班 
	int maxn=1;
	for(int i=1;i<=inFlight;i++){
		if(q.empty()){
			Push1(i,1);inSum[1]++;
			continue;
		}//如果没有廊桥占用,分配第一个廊桥 
		if(-q.top().first<inTime[i].arrive&&!q.empty()){
			//如果在航班到达时有空位 
			int cur=0x7fffffff;
			do{//将所有已起飞的航班出队,并寻找编号最小的空闲廊桥 
				cur=min(q.top().second,cur);
				q.pop();
			}while(-q.top().first<inTime[i].arrive&&!q.empty());
			Push1(i,cur);inSum[cur]++;
			continue;
		}
		else {//分配后一个廊桥 
			Push1(i,++maxn);inSum[maxn]++;
			continue;
		}
	}
	for(int i=2;i<=n;i++){
		inSum[i]=inSum[i]+inSum[i-1];
	}//将inSum[1...i]叠加 
	while(!q.empty())q.pop();maxn=1;//清空
	//操作同上 
	for(int i=1;i<=outFlight;i++){
		if(q.empty()){
			Push2(i,1);outSum[1]++;
			continue;
		}
		if(-q.top().first<outTime[i].arrive&&!q.empty()){
			int cur=0x7fffffff;
			do{
				cur=min(q.top().second,cur);
				q.pop();
			}while(-q.top().first<outTime[i].arrive&&!q.empty());
			Push2(i,cur);outSum[cur]++;
			continue;
		}
		else {
			Push2(i,++maxn);outSum[maxn]++;
			continue;
		}
	}
	for(int i=2;i<=n;i++){
		outSum[i]=outSum[i]+outSum[i-1];
	}
	
	for(int i=0;i<=n;i++){
		inBridge=i;outBridge=n-i;
		int res=inSum[inBridge]+outSum[outBridge];
		ans=max(res,ans);
	}//枚举每种分配情况,找到最大情况 
	printf("%d",ans);
	
	return 0;
}

[测试记录]献上(https://www.luogu.com.cn/record/128285214)

2023/10/9 17:54
加载中...