题解：CF1949G Scooter

直接贪心即可。

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

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

CPP

3
-MCM
M-MC

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

由于每次至少匹配一个人，时间复杂度

O(n^2)

，可以做到

O(n)

。

CPP

#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;
}

题解：CF1949G Scooter

文章操作

相关推荐

评论

题解：CF1949G Scooter