社区讨论
15pts,样例1、2已过,思路是否有错
P7913[CSP-S 2021] 廊桥分配参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @m2o3fd9o
- 此快照首次捕获于
- 2024/10/25 10:08 去年
- 此快照最后确认于
- 2025/11/04 16:15 4 个月前
每次只看所有廊桥中停靠的飞机离开时间最靠前的那个
CPP#include <iostream>
#include <utility>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N=100005;
int n,m1,m2;
int f1[N],f2[N];
PII p1[N],p2[N]; //国内航班,国际航班
bool cmp(PII x,PII y)
{
return x.first < y.first;
}
int work(PII p[],int m,int x) //国内/国际的航班、几个航班、有x个廊桥
{
queue<int> q; //只需记录离开时间
if(x==0) return 0;
int cnt=0,ans=0,lea=0; //占用了几个廊桥+进来几个飞机
for(int i=1;i<=m;i++)
{
if(i==1) q.push(p[i].second),cnt++,ans++,lea=p[i].second;
else{
if(p[i].first>=lea) //更新廊桥优先,不会占用
{
lea=min(lea,p[i].second);
q.pop(),q.push(p[i].second),ans++;
}
else{ //如果非要占用
if(cnt>=x) continue; //无法占用新廊桥
ans++,cnt++,q.push(p[i].second);
lea=min(lea,p[i].second);
}
}
}
return ans;
}
int main()
{
scanf("%d%d%d",&n,&m1,&m2);
for(int i=1;i<=m1;i++)
scanf("%d%d",&p1[i].first,&p1[i].second);
for(int j=1;j<=m2;j++)
scanf("%d%d",&p2[j].first,&p2[j].second);
sort(p1+1,p1+m1+1,cmp);
sort(p2+1,p2+m2+1,cmp);
int ansmax=-1;
for(int i=0;i<=n;i++)
ansmax=max(ansmax,work(p1,m1,i)+work(p2,m2,n-i));
printf("%d",ansmax);
}
回复
共 0 条回复,欢迎继续交流。
正在加载回复...