Codeforces Round #547 (Div. 3) D. Colored Boots (贪心,模拟)

题意:有两个字符串,两个字符串中的相同字符可以相互匹配,\(?\)可以和任意字符匹配,输出最大匹配的字符数量和它们分别两个字符串中的位置.
题解:很容易贪心,我们先遍历第一个字符串,然后在第二个字符串中去找与当前位置相同的字符,这个过程我们可以先将每个字符的位置存下来然后再操作,遍历完后再遍历字符和问号,最后是问号和问号匹配,具体看代码吧,主要是想学习一下用队列来模拟操作(会方便很多).

代码:

int n;

string l,r;

queue<int> h1[30],h2[30];

vector<PII> ans;

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    cin>>n;

    cin>>l>>r;

    rep(i,0,n-1){

    	if(l[i]=='?') h1[0].push(i+1);

    	else h1[l[i]-96].push(i+1);

    	if(r[i]=='?') h2[0].push(i+1);

    	else h2[r[i]-96].push(i+1);

    }

    rep(i,1,26){

    	int mi=min(h1[i].size(),h2[i].size());

    	rep(j,1,mi){

    		ans.pb({h1[i].front(),h2[i].front()});

    		h1[i].pop();

    		h2[i].pop();

    	}

    }

    rep(i,1,26){

    	int mi=min(h1[0].size(),h2[i].size());

    	rep(j,1,mi){

    		ans.pb({h1[0].front(),h2[i].front()});

    		h1[0].pop();

    		h2[i].pop();

    	}

    }

    rep(i,1,26){

    	int mi=min(h1[i].size(),h2[0].size());

    	rep(j,1,mi){

    		ans.pb({h1[i].front(),h2[0].front()});

    		h1[i].pop();

    		h2[0].pop();

    	}

    }

    int mi=min(h1[0].size(),h2[0].size());

    rep(i,1,mi){

    	ans.pb({h1[0].front(),h2[0].front()});

    	h1[0].pop();

    	h2[0].pop();

    }

    cout<<(int)ans.size()<<'\n';

    rep(i,0,(int)ans.size()-1) cout<<ans[i].fi<<' '<<ans[i].se<<'\n';

    return 0;

}

巴特西

Codeforces Round #547 (Div. 3) D. Colored Boots (贪心,模拟)

最新文章

热门文章