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; }