题解

天随游子 · 2021-10-30 10:12:48 · 个人记录

题

开始水我的第一篇题解，各位大佬不喜勿喷，谢谢

话说我比赛T1爆零，是怎么有勇气在这里水题解的

正文

1. 思路

拿到题目，我们可以看到：很难...

于是我们继续看，再看...

对于每一架飞机，你会选择飞到最小的空闲的廊桥。

所以，当有足够的廊桥时，提供的廊桥数量不影响当前飞机停下的廊桥编号, 也就是说，停到远机位可以和新加一个廊桥一样操作。

于是，我们得到了思路：

1. 假设廊桥足够多，预处理出每架飞机停的廊桥的编号c [ i ]； c [ i ] = 当前第一个空廊桥的编号 p ；

2. 用 t [ j ] 表示 c [ i ] == j 的个数; 再算出前缀和 s [ i ]

3. 像这样算出ans

for(int i=0;i<=n;i++) 
        ans=max(ans,s[i]+s1[n-i]);

2.代码

#include<bits/stdc++.h>
#define N 100729
using namespace std;
int n,m1,m2,ans=-1,p;
int t[N],s[N],c[N],re[N],re1[N];
int t1[N],s1[N],c1[N];
struct dl{
    int a,b;
}d[N],d1[N];
struct njx{
    int d,id;
    bool operator < (const njx&b) const { return d>b.d; }
}tmp;
priority_queue <njx> q;
bool cmp(dl a,dl b) { return a.a<b.a; }
int main() {
    scanf("%d%d%d",&n,&m1,&m2);
    for(int i=1;i<=m1;i++) 
        scanf("%d%d",&d[i].a,&d[i].b);
    for(int i=1;i<=m2;i++) 
        scanf("%d%d",&d1[i].a,&d1[i].b);    
    sort(d+1,d+m1+1,cmp); sort(d1+1,d1+m2+1,cmp);
    tmp.d=(1<<30),tmp.id=(1<<30); q.push(tmp); 
    p=1;
    for(int i=1;i<=m1;i++) {
        while(d[i].a>q.top().d) {
                int tmp=q.top().id; 
                p=min(p,tmp); re[tmp]=0; q.pop();
            }
        re[p]=1; c[i]=p;
        tmp.d=d[i].b; tmp.id=p; q.push(tmp);
        while(re[p]) ++p;
    }
    while(!q.empty()) q.pop();
    tmp.d=(1<<30),tmp.id=(1<<30); q.push(tmp); 
    p=1;
    for(int i=1;i<=m2;i++) {
        while(d1[i].a>q.top().d) {
            int tmp=q.top().id; 
            p=min(p,tmp); re1[tmp]=0; q.pop();
        }
        re1[p]=1; c1[i]=p; 
        tmp.d=d1[i].b; tmp.id=p; q.push(tmp);
        while(re1[p]) ++p;
    }
    for(int i=1;i<=m1;i++) ++t[c[i]];
    for(int i=1;i<=m2;i++) ++t1[c1[i]];
    for(int i=1;i<=m1;i++) s[i]=s[i-1]+t[i];
    for(int i=1;i<=m2;i++) s1[i]=s1[i-1]+t1[i];
    for(int i=0;i<=n;i++) 
        ans=max(ans,s[i]+s1[n-i]);
    printf("%d",ans);
    return 0;
}