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;
}