Educational Codeforces Round 75 C Minimize The Integer

这道题的意思就是给出一个由数字组成的字符串，相邻的数字可以互换位置，但是如果相邻的为同奇同偶这样就不能交换。让我们求交换任意次数可以产生的最小数。

这条限制就是说明了，奇数偶数的相对顺序是不能变的，这道题主要是找不变量，如果把这一点相通了就好理解，我们分别把奇数和偶数取出来，要使最后得数最小就要是最高位的数字尽可能小，所以每次取两个队列小的那一个输出就好了。

AC代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<iomanip>
#include<math.h>
using namespace std;
typedef long long ll;
typedef double ld;
const int INF = 1e9;
int i,j,k;
const int N = 300010;
int q,n,res;
char s[N];
int main()
{
    cin>>q;
    getchar();
    while(q--)
    {
        scanf("%s",s);
        int len=strlen(s);
        queue<char>ans1;
        queue<char>ans2;
        for(i=0; i<len; i++)
        {
            res=s[i]-'a';
            if(res&1)
                ans1.push(s[i]);
            else
                ans2.push(s[i]);
        }
        for(i=0; i<len; i++)
        {
            if((ans2.empty()||ans1.front()<ans2.front())&&!ans1.empty())
            {
                cout<<ans1.front();
                ans1.pop();
            }
            else
            {
                cout<<ans2.front();
                ans2.pop();
            }
        }
        cout<<endl;
    }
    return 0;
}