YTU 2555: 老大的烦恼

时间:2021-12-31 04:51:38

2555: 老大的烦恼

时间限制: 1 Sec   内存限制: 128 MB
提交: 176   解决: 47

题目描述

万恶的小黑,布置了一道题给老大做:给你一个n位的数,现在要求 你随意删除m位后,任意改变顺序,输出其能够构成的最小有效整数(即不能有前导零,如果只含有0则输出0)。但是,这正赶上了老大的对象从故乡来看他,老 大怎么能丢失这种机会呢。所以他找你寻求帮助,帮他完成这个问题吧。

输入

输入包含T组数据。每组数据包含两行,第一行包含两个整数n和m,代表一个数的位数和要删除的位数个数;第二行为一个n位的整数;(0<=m<n<5000)

输出

每组数据输出一行,表示删除后能够构成的最小整数

样例输入

2
5 2
54321
5 4
42130

样例输出

123
0

迷失在幽谷中的鸟儿,独自飞翔在这偌大的天地间,却不知自己该飞往何方……

#include <iostream>
#include <stdlib.h>
using namespace std;
int cmp1(const void *a,const void *b)
{
    return *(char *)b-*(char *)a;
}
int cmp2(const void *a,const void *b)
{
    return *(char *)a-*(char *)b;
}
int main()
{
    int t,n,m,i,j,c,k,s,g;
    char a[5005],b[5005];
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(i=0; i<n; i++)
            cin>>a[i];
        qsort(a,n,sizeof(a[0]),cmp1);
        c=0;
        for(i=m; i<n; i++)
            b[c++]=a[i];
        qsort(b,c,sizeof(b[0]),cmp2);
        k=0,s=0;
        for(i=0; i<c; i++)
            if(b[i]=='0')
            {
                k=1;
                s=s+k;
            }
        if(s==c) cout<<"0";
        else
        {
            for(i=0; i<c; i++)
                if(b[i]!='0')
                {
                    g=i;
                    break;
                }
            cout<<b[g];
            for(j=0; j<c; j++)
            {
                if(j==g)continue;
                cout<<b[j];
            }
        }
        cout<<endl;
    }
    return 0;
}