codeforces1141D Colored Boots(暴力+贪心)

给出两个长度为 n(1≤n≤150000)的仅含有小写字母和'?'的字符串，询问两个字符串最多能有几对匹配的字符。
(每个字母都可以与和它相同的字符匹配，'?'可以与任意字符匹配，匹配与位置无关)
输出最大匹配对数，以及每一对中两个字符在字符串中的位置

/*
 * codeforces1141D Colored Boots 
 * Created by hao on 2019/4/11.
 * 给出两个长度为 n(1≤n≤150000)的仅含有小写字母和'?'的字符串，询问两个字符串最多能有几对匹配的字符。
 * （每个字母都可以与和它相同的字符匹配，'?'可以与任意字符匹配，匹配与位置无关）
 * 输出最大匹配对数，以及每一对中两个字符在字符串中的位置
 */
#include <cstdio>
#include <cstring>
#include<iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>

using namespace std;
#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define pub push_back
#define pob pop_back()
#define pof pop_front()
vector<int> l[250], r[250];
vector<pair<int, int> > ans;

int main() {
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    string s1, s2;
    cin >> s1 >> s2;
    //让每一个字符对应自己的位置(下表+1)
    for (int i = 0; i < s1.length(); i++) {
        l[(int) s1[i]].pub(i + 1);
    }
    for (int i = 0; i < s2.length(); i++) {
        r[(int) s2[i]].pub(i + 1);
    }
    //记录'?'对应的int值，防止'?'和'?'优先匹配
    int q = (int) '?';
    for (int i = 0; i < 250; i++) {
        //等于'?'时跳过，防止'?'优先匹配。
        if (i == q) continue;
        //匹配相同的字符，比如'a','a','b','b'
        while (!l[i].empty() && !r[i].empty()) {
            ans.pub(mp(l[i].back(), r[i].back()));
            l[i].pob;
            r[i].pob;
        }
        //让第一个字符串的'?'和第二个字符串的任意字符匹配
        while (!l[q].empty() && !r[i].empty()) {
            ans.pub(mp(l[q].back(), r[i].back()));
            l[q].pob;
            r[i].pob;
        }
        //让第一个字符串的任意字符和第二个字符串的'?'匹配
        while (!l[i].empty() && !r[q].empty()) {
            ans.pub(mp(l[i].back(), r[q].back()));
            l[i].pob;
            r[q].pob;
        }
    }
    //在所有的除去'?'的字符都处理完之后，处理'?'和'?'的情况
    while (!l[q].empty() && !r[q].empty()) {
        ans.pub({l[q].back(), r[q].back()});
        l[q].pob;
        r[q].pob;
    }
    //输出匹配对数
    cout << ans.size() << endl;
    //输出匹配的对数的相应的两个位置
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i].ff << " " << ans[i].ss << endl;
    }

    return 0;
}