我考场上通过枚举每一种可能的分配情况,然后再通过数组排序模拟廊桥的飞机停靠情况(还没有分配完则继续分配,已分配完则排序,并将cnt归零,开始新一轮分配,具体见代码)
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
struct node{int t1,t2;};
node inner[100005],outer[100005];
int ocu1[100005],ocu2[100005];
bool cmp(node x,node y){
if(x.t1!=y.t1) return x.t1<y.t1;
return x.t2<y.t2;
}
int main(){
freopen("airport.in","r",stdin);
freopen("airport.out","w",stdout);
int n,m1,m2;
cin>>n>>m1>>m2;
if(n<=5000 and m1+m2<=5000){
for(int i=1;i<=m1;i++)cin>>inner[i].t1>>inner[i].t2;//国内
for(int i=1;i<=m2;i++)cin>>outer[i].t1>>outer[i].t2;//国际
sort(inner+1,inner+m1+1,cmp);//按时间排序,便于模拟
sort(outer+1,outer+m2+1,cmp);
int res=-1;//答案
for(int i=0;i<=n;i++){
int in=i,out=n-i;
int cnt=0;
int ans1=0,ans2=0;//统计答案
if(in!=0)for(int j=1;j<=m1;j++){
if(ocu1[++cnt]<=inner[j].t1){
ocu1[cnt]=inner[j].t2;
ans1++;
}//如果还没有分配完则接着分配
if(cnt==in){
sort(ocu1+1,ocu1+in+1);
cnt=0;
}//分配完后则按照时间顺序,开始新一轮分配
}
cnt=0;
if(out!=0)for(int j=1;j<=m2;j++){
if(ocu2[++cnt]<=outer[j].t1){
ocu2[cnt]=outer[j].t2;
ans2++;
}
if(cnt==out){
sort(ocu2+1,ocu2+out+1);
cnt=0;
}
}
res=max(res,ans1+ans2);
memset(ocu1,0,sizeof(ocu1));
memset(ocu2,0,sizeof(ocu2));
}
cout<<res<<endl;
}
}
但是这样做有一个问题:每一轮枚举时不能保证判断到时间最短的那一种情况,不出所料,该思路零分。 我朋友在考场上使用了优先队列,保证每一次都能取出最早空闲的廊桥。此代码40分 (码风略微清奇,但至少写对了)
#include<bits/stdc++.h>
using namespace std;
int n, m1, m2, ans = -1;
struct pla1{//国内数据
int x, y;
}p1[100003];
struct pla2{//国际数据
int x, y;
}p2[100003];
priority_queue <int, vector<int>, greater<int> > q1;
priority_queue <int, vector<int>, greater<int> > q2;
bool cmp1(pla1 a, pla1 b){
return a.x < b.x;
}
bool cmp2(pla2 a, pla2 b){
return a.x < b.x;
}
int main()
{
freopen("airport.in", "r", stdin);
freopen("airport.out", "w", stdout);
cin >> n >> m1 >> m2;
for(int i = 1; i <= m1; i++)
scanf("%d%d", &p1[i].x, &p1[i].y);//国内航班
for(int i = 1; i <= m2; i++)
scanf("%d%d", &p2[i].x, &p2[i].y);//国际航班
sort(p1, p1 + m1 + 1, cmp1);
sort(p2, p2 + m2 + 1, cmp2);
for(int i = 0; i <= n; i++){
int cnt = 0;
while(!q1.empty())
q1.pop();
while(!q2.empty())
q2.pop();//清空
for(int j = 1; j <= m1; j++){
if(q1.empty() == true && i > 0){
q1.push(p1[j].y);
cnt++;
continue;
}//当队列空时就加入元素
if(q1.empty() == true)
break;
while(!(q1.empty() == true) && p1[j].x >= q1.top())
q1.pop();//将所有已结束使用的廊桥弹出
if(i > q1.size()){
q1.push(p1[j].y);
cnt++;
}
else
continue;
}
for(int j = 1; j <= m2; j++){
if(q2.empty() == true && n - i > 0){
q2.push(p2[j].y);
cnt++;
continue;
}
if(q2.empty() == true)
break;
while(!(q2.empty() == true) && p2[j].x >= q2.top())
q2.pop();
if(n - i > q2.size()){
q2.push(p2[j].y);
cnt++;
}
else
continue;
}
ans = max(ans, cnt);
}
cout << ans;
return 0;
}