社区讨论

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 条回复,欢迎继续交流。

正在加载回复...