CodeForces - 1251C （思维+贪心+归并排序）

题意

https://vjudge.net/problem/CodeForces-1251C

一个字符串，相邻的偶数奇数不能交换位置，其他相邻的情况可以交换，问字符串代表的数最小是多少。

思路

相邻的偶数、奇数位置固定，所以可以把奇数放到一起，偶数放到一起，对这两堆归并排序即可。

代码

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3f3f3f3f

#define ll long long

const int N=200005;

const int mod=1e9+7;

const double eps=1e-8;

const double PI = acos(-1.0);

#define lowbit(x) (x&(-x))

ll gcd(ll a,ll b){return b==0?a:gcd(b,a%b);}

ll qpow(ll a,ll b){ll res=1;while(b){if(b&1) res=res*a%mod;a=a*a%mod;b>>=1;}return res;}

ll inv(ll a,ll p){return qpow(a,p-2);}

int main()

{

    std::ios::sync_with_stdio(false);

    int t;

    cin>>t;

    while(t--)

    {

        string s;

        cin>>s;

        string ji,ou;

        int l=s.length();

        for(int i=0;i<l;i++)

        {

            if((s[i]-'0')%2)

                ji+=s[i];

            else

                ou+=s[i];

        }

        int i=0,j=0,li=ji.length(),lj=ou.length();

        while(i<li&&j<lj)

        {

            if(ji[i]<ou[j])

            {

                cout<<ji[i];

                i++;

            }

            else

            {

                cout<<ou[j];

                j++;

            }

        }

        while(i<li)

            cout<<ji[i++];

        while(j<lj)

            cout<<ou[j++];

        cout<<endl;

    }

    return 0;

}