Gym – 100507H H. Pair: normal and paranormal 栈

H - Pair: normal and paranormal 栈

Source

Gym - 100507H

My Solution

题意：给一个字符串，要求把大写字母和小写字母一一配对，要求不交叉。

用栈来模拟，不要写挂了就没问题，^_^
复杂度 O(n)

#include 
#include 
#include 
#include 
using namespace std;
typedef long long LL;
typedef pair<char, int> pci;
const int maxn = 5e3 + 8;

string s;
int Ind[2*maxn], ans[maxn];
stack sta;
int main()
{
    #ifdef LOCAL
    freopen("h.txt", "r", stdin);
    //freopen("h.out", "w", stdout);
    int T = 4;
    while(T--){
    #endif // LOCAL
    ios::sync_with_stdio(false); cin.tie(0);

    int n, ptr = 0, a = 0, A = 0;
    cin >> n >> s;
    for(int i = 0; i < 2*n; i++){if(islower(s[i])) Ind[i] = ++ a; else Ind[i] = ++ A; }
    for(int i = 0; i < 2*n; i++){
        if(!sta.empty() && isupper(sta.top().first) && tolower(sta.top().first) == s[i]){
            ans[Ind[sta.top().second]] = Ind[i];
            sta.pop();
        }
        else if(!sta.empty() && isupper(s[i]) && sta.top().first == tolower(s[i])){
            ans[Ind[i]] = Ind[sta.top().second];
            sta.pop();
        }
        else sta.push(pci(s[i], i));
    }
    if(sta.empty()){
        cout << ans[1];
        for(int i = 2; i <= n; i++){
            cout << " " << ans[i];
        }
    }
    else cout << "Impossible";
    cout << endl;

    #ifdef LOCAL
    while(!sta.empty()) sta.pop();
    cout << endl;
    }
    #endif // LOCAL
    return 0;
}