【CodeForces 1251C --- Minimize The Integer】-程序员宅基地

技术标签： ACM Minimize The Integer CodeForces 1251C

【CodeForces 1251C --- Minimize The Integer】

Description

You are given a huge integer a consisting of n digits (n is between 1 and 3⋅105, inclusive). It may contain leading zeros.

You can swap two digits on adjacent (neighboring) positions if the swapping digits are of different parity (that is, they have different remainders when divided by 2).

For example, if a=032867235 you can get the following integers in a single operation:

302867235 if you swap the first and the second digits;
023867235 if you swap the second and the third digits;
032876235 if you swap the fifth and the sixth digits;
032862735 if you swap the sixth and the seventh digits;
032867325 if you swap the seventh and the eighth digits.

Note, that you can’t swap digits on positions 2 and 4 because the positions are not adjacent. Also, you can’t swap digits on positions 3 and 4 because the digits have the same parity.

You can perform any number (possibly, zero) of such operations.

Find the minimum integer you can obtain.

Note that the resulting integer also may contain leading zeros.

Input

The first line contains one integer t (1≤t≤104) — the number of test cases in the input.

The only line of each test case contains the integer a, its length n is between 1 and 3⋅105, inclusive.

It is guaranteed that the sum of all values n does not exceed 3⋅105.

Output

For each test case print line — the minimum integer you can obtain.

Sample Input

3
0709
1337
246432

Sample Output

0079
1337
234642

Note

In the first test case, you can perform the following sequence of operations (the pair of swapped digits is highlighted): 070−−9→0079.

In the second test case, the initial integer is optimal.

In the third test case you can perform the following sequence of operations: 24643−−2→2463−−42→243−−642→234642.

解题思路：

根据题意我们可以理解为相同奇偶性的数字顺序是不能变的，能变得只是不同奇偶性的数字。
所以我们可以通过两个队列来分别按顺序存储奇数和偶数，然后判断大小依次输出就行。

AC代码：

#include <iostream>
#include <string>
#include <queue>
using namespace std;
#define SIS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)

int main()
{
    
    SIS;
    string s;
    queue<char> q1,q2;
    int T;
    cin >> T;
    while(T--)
    {
    
        string ans;
        cin >> s;
        int len=s.size();
        for(int i=0;i<len;i++)
        {
    
            if(s[i]&1) q1.push(s[i]);
            else q2.push(s[i]);
        }
        while(!q1.empty() || !q2.empty())
        {
    
            if(q1.empty() || (!q2.empty() && q1.front()>q2.front()))
            {
    
                ans.push_back(q2.front());
                q2.pop();
            }
            else
            {
    
                ans.push_back(q1.front());
                q1.pop();
            }
        }
        cout << ans << endl;
    }
    return 0;
}

本文链接：https://blog.csdn.net/qq_41879343/article/details/102745652

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

BPI-Bit 开发板带有Xtensa 32位LX6双核处理器的嵌入式系统的ESP 32_xtensa lx6-程序员宅基地

文章浏览阅读1.7k次。BPI:bit（也称为BPI-bit，作为webduino:bit）是一个带有Xtensa 32位LX6双核处理器的嵌入式系统的ESP 32。支持Webduino、Arduino、微python以及Scratch X编程环境。BPI:一些开发板5厘米宽5厘米长,重约10 ~ 12克,除了以下20销金手指接口,内置一个25全彩LED照明矩阵,两个光敏电阻按钮开关温度传感电阻蜂鸣器和九轴传感器(三轴加速度三轴陀螺仪和三轴磁罗盘),空间配置如下:全色LED矩阵：4光敏传感器：36（左）39（A3右上）按钮_xtensa lx6

2017界面UI设计风格流行什么？（二）_ui界面设计风格线性化-程序员宅基地

文章浏览阅读373次。那么卡片化呢？如果你的想法创意还停留在卡片阶段，那就落伍了，因为无框界面的发展过程中，卡片逐渐被淡化。卡片是否有存在的必要？用户更多的不会去关注，他们只注意来这里的最终功能所在，界面对他们来讲或许只是寻求信息的方式。没错，卡片化的由来有它一定的道理。几年前大家注意到显示屏的尺寸越来越不可预期，设计师也需要一种方式来让设计出的界面能够适应不同尺寸的屏幕。卡片刚好能够解决这一_ui界面设计风格线性化

CRC循环校验码的系统仿真及其应用_simulink modbus crc16 检验模块-程序员宅基地

文章浏览阅读2.7k次，点赞7次，收藏40次。CRC即循环冗余校验码，是数据通信领域中最常用的一种检错校验码，其特征是信息字段和校验字段的长度可以任意选定，循环冗余检查是一种数据传输检错功能，对数据进行多项式计算，并将得到的结果附在帧的后面，接收设备也执行类似的算法，以保证数据传输的正确性和完整性循环冗余码CRC检验技术广泛应用于测控及通信领域。CRC计算可以靠专用的硬件来实现，但是对于低成本的微控制器系统，在没有硬件支持下实现CRC检验，关键的问题就是如何通过软件来完成CRC计算，也就是CRC算法的问题。_simulink modbus crc16 检验模块

Food Buying（CF-1296B）_t 组数据,每组给出 1 个数 n,代表有 n 元钱,现在用这 n 元钱买东西,每买 10 元返-程序员宅基地

文章浏览阅读789次。Problem DescriptionMishka wants to buy some food in the nearby shop. Initially, he has s burles on his card.Mishka can perform the following operation any number of times (possibly, zero): choose..._t 组数据,每组给出 1 个数 n,代表有 n 元钱,现在用这 n 元钱买东西,每买 10 元返

JSP内置对象、表达式和标签及JSP解析原理-程序员宅基地

文章浏览阅读1k次。JSP的学习路线什么是JSP？——JSP的背景和发展情况简介为什么要用JSP？——普通HTML编程中，我们遇到的了哪些问题？ JSP的语法特点简介 JSP内置对象 EL表达式 JSP的标签式语法（指令和动作） JSTL标签库 JSP的解析编译执行过程* 什么是JSP？1.Java Server Pages(JSP) is a technology thathelps software develop...

ESP32开发-LVGL动画显示_lv_snprintf-程序员宅基地

文章浏览阅读4.4k次。LVGL动画LVGL 支持动态效果，包括动态切换屏幕，组件动画效果等等。动画创建步骤以及API说明以官方demo中的动画创建为例 //定义动画变量 lv_anim_t a; //初始化动画变量 lv_anim_init(&a); //设置要进行动画处理的组件 lv_anim_set_var(&a, gauge); //设置动画功能 lv_anim_set_exec_cb(&a, (lv_anim_exec_xcb_t_lv_snprintf