Bài D - Codeforces Round #547 (Div.3)

Bài D: 
Đề bài: Có n chiếc giày trái và n chiếc giày phải. Mỗi chiếc có một màu được ký hiệu bởi 1 chữ cái latin thường hoặc một dấu hỏi (?). Vì vậy, bạn được cho 2 xâu l và r, cả hai đều có độ dài là n. Kí tự l(i) tượng trưng cho màu sắc của chiếc giày trái thứ i và kí tự r(i) tượng trưng cho màu sắc của chiếc giày phải thứ i.
  Một chữ cái Latin kí hiệu một màu xác định, và dấu hỏi ? tượng trưng cho màu chưa xác định. Hai màu riêng biệt được gọi là tương thích nếu chúng giống nhau hoàn toàn. Một màu chưa xác định thì tương thích với bất kì màu xác định hoặc màu chưa xưa định.
 Ví dụ, cặp màu dưới đây là tương thích: ('f','f'),('?','z'),('a','?') và ('?','?'). Các cặp dưới đây là không tương thích ('f','g') và ('a','z').
 Xác định số cặp giày tối đa thỏa mãn một chiếc giày trái và một chiếc giày phải cùng một cặp và màu sắc của chúng tương thích với nhau.
Đầu vào:
+ Dòng đầu tiên là số n (1<=n<=150000), kí hiệu số giày mỗi bên.
+Dòng thứ hai chứa xâu l với độ dài n
+Dòng thứ ba chứa xâu r với độ dài n.
Đầu ra:  
+ In ra số k - là số cặp giày lớn nhất tương thích với nhau (một chiếc bên trái, một chiếc bên phải).
+ k dòng tiếp theo chứa cặp a(j),b(j). Dòng thứ j chứa chỉ số a(j) của giày trái trong cặp thứ j và chỉ số b(j) của giày phải trong cặp thứ j. Tất cả các số a(j) phải phân biệt, tất cả các số b(j) phải phân biệt.
+ Nếu có nhiều câu trả lời, in ra đáp án bất kì.
Ví dụ:
đầu vào:
10
codeforces
dodivthree
đầu ra:
5
7 8
4 9
2 2
9 10
3 1
.
Hướng dẫn: Ta sử dụng phương pháp tham lam tiếp cận bài toán này. Đầu tiên, nối những cặp mà có màu sắc giống nhau (và chúng xác định, không phải vô định). Sau đó ta nối mỗi chiếc giày có màu vô định bên trái với một chiếc giày xác định bên phải.Có thể, một vài chiếc giày vô định bên trái chưa được nối. Tương tự, nối mỗi chiếc giày vô định (bất kì) bên phải với một chiếc giày xác định bên trái (bất kì). Và cuối cùng nối các chiếc giày vô định bên trái với các chiếc giày vô định bên phải (bất kì).
Lời giải:

#include<bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<int(n);i++)
const int A=26;
int main(){
   int n;
   cin>>n;
   string l;
   cin>>l;
   vector<vector<int>> left(A);
   vector<int> wl;
   forn(i,n)
     if(l[i]!='?') left[l[i]-'a'].push_back(i);
     else
        wl.push_back(i);
    string r;
    cin>>r;
    vector<vector<int>> right(A);
    vector<int> wr;
    forn(i,n)
      if(r[i]!='?') right[r[i]-'a'].push_back(i);
      else
         wr.push_back(i);
      vector<pair<int,int>> p;
      vector<int> cl(A),cr(A);
    forn(i,A){
       forn(j,min(left[i].size(),right[i].size()))
         p.push_back(make_pair(left[i][j]+1,right[i][j]+1));
        cl[i]=cr[i]=min(left[i].size(),right[i].size());
    }
   forn(i,A)
     while(cl[i]<left[i].size()&&!wr.empty()){
        p.push_back(make_pair(left[i][cl[i]]+1,wr[wr.size()-1]+1));
        cl[i]++;
        wr.pop_back();
     }
    forn(i,A)
     while(cr[i]<right[i].size()&&!wl.empty()){
        p.push_back(make_pair(wl[wl.size()-1]+1,right[i][cr[i]]+1));
        wl.pop_back();
        cr[i]++;
     }
     forn(j,min(wl.size(),wr.size()))
       p.push_back(make_pair(wl[j]+1,wr[j]+1));
       cout<<p.size()<<endl;
    for(auto pp:p)
          cout<<pp.first<<" "<<pp.second<<endl;
    return 0;
}