2015 湘潭大学程序设计比赛（Internet）--D题-最小的数

浏览数：43 / 时间：2015年06月09日

最小的数
Accepted : 47		Submit : 276
Time Limit : 1000 MS		Memory Limit : 65536 KB

题目描述

给你一个n位数，每次操作可以选该数任意的相邻两位进行交换，如果最多可以操作k次,那么最终可以得到的最小的数是什么

（n位且不能含前导零)？

输入

有多组测试数据，第一行为数据个数T(T<=10); 每组数据占一行，包含一个数(不超过1000位)和k(0<=k<=1000)，中间用空格隔开;

输出

最终能得到的最小的数。

样例输入

2
321654987 1
321654987 2

样例输出

231654987
132654987

Source

WCB

http://202.197.224.59/OnlineJudge2/index.php/Problem/read/id/1228

思路：从第一位向后找m次，如果遇到比第一位小的则把它放到前面，同时让m减去相对应移动的次数，然后从第二位开始找，第三位，第四位。。。；

代码如下：

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 1050
using namespace std;
int main()
{
    int T,i,m,j,k;
    char str[N];
    scanf("%d",&T);
    while(T--)
    {
        scanf("%s %d",str,&m);
        for(i=0;str[i];i++)
        {
            k=i;
            for(j=i+1;j<=i+m&&str[j];j++)
            {
                if(i==0&&str[j]==‘0‘)
                    continue;
                if(str[j]<str[k])
                    k=j;
            }
            if(k!=i)
            {
                char ch=str[k];
                for(j=k;j>i;j--)
                    str[j]=str[j-1];
                str[j]=ch;
                m-=(k-i);
            }
        }
        printf("%s\n",str);
    }
    return 0;
}