《 警 示 后 人 》(关于本题的正确骗分思路)
查看原帖
《 警 示 后 人 》(关于本题的正确骗分思路)
383601
shijihong楼主2021/10/25 20:07

我考场上通过枚举每一种可能的分配情况,然后再通过数组排序模拟廊桥的飞机停靠情况(还没有分配完则继续分配,已分配完则排序,并将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;
}
2021/10/25 20:07
加载中...