题解：CF1949G Scooter

· · 题解

直接贪心即可。

首先，如果教学楼已经完成匹配或无限制无教授，显然可以不考虑。

注意到开始一定在没有限制的教学楼接人，然后考虑将人送到哪里。我们贪心地希望能在放人的同时接更多人，否则可以给出如下构造：

3
-MCM
M-MC

此时如果将 1 和 2 匹配则无法继续匹配，因为并没有接到尽量多的人。另一方面，如果连当前人的对应教学楼都不存在，也可以类似地贪心。

由于每次至少匹配一个人，时间复杂度 O(n^2)，可以做到 O(n)。

#include<bits/stdc++.h>
#define maxn 1010005
#define fi first
#define se second
#define pii pair<int,int>
#define sqr(x) ((x)*(x))
#define pc(x) putchar(x)
#define lowbit(x) ((x)&-(x))
#define conc(x,y,w) son[x][w]=y,fa[y]=x
//#define int long long
inline int min(int x,int y){return x<y?x:y;}
inline int max(int x,int y){return x<y?y:x;}
using namespace std;
typedef long long ll;
mt19937 yrand(time(0));
const int Mod=998244353,inf=1e9,N=1e6,Inv=(Mod+1)/2,B=447;

int n,vis[maxn];
char c1[maxn],c2[maxn];
vector<pair<string,int> >ans;
void solve(){
    cin>>n>>c1>>c2;
    char cur=0;
    while(1){
        for(int i=1;i<=n;i++){
            if(c1[i-1]==c2[i-1]) vis[i]=1;
            if(vis[i]) continue;
            if(c1[i-1]=='-'){
                ans.emplace_back("DRIVE",i);
                ans.emplace_back("PICKUP",0);
                cur=c2[i-1];
                vis[i]=1;
                c2[i-1]='-';
                break;
            }
        }
        if(!cur) break;
        while(cur){
            int fl1=0,fl2=0,fl3=0;
            for(int i=1;i<=n;i++){
                if(c1[i-1]==c2[i-1]) vis[i]=1;
                if(vis[i]) continue;
                if(c1[i-1]=='-') fl3=i;
                if(c1[i-1]!=cur) continue;
                if(c2[i-1]=='-') fl2=i;
                else fl1=i;
            }
            int x=(fl1?fl1:(fl2?fl2:fl3));
            if(!x){cur=0;break;}
            ans.emplace_back("DRIVE",x);
            ans.emplace_back("DROPOFF",0);
            vis[x]=1;
            if(c2[x-1]=='-'){cur=0;break;}
            cur=c2[x-1];
            ans.emplace_back("PICKUP",0); 
        }
    }
    int len=ans.size();
    cout<<len<<'\n';
    for(auto i:ans){
        cout<<i.fi;
        if(i.se) cout<<' '<<i.se;
        cout<<'\n';
    }
}

signed main(){
    solve();
    return 0;
}