老大的烦恼
时间： 1ms 内存：128M
描述：
万恶的小黑，布置了一道题给老大做：给你一个n位的数，现在要求 你随意删除m位后，任意改变顺序，输出其能够构成的最小有效整数(即不能有前导零,如果只含有0则输出0)。但是，这正赶上了老大的对象从故乡来看他，老 大怎么能丢失这种机会呢。所以他找你寻求帮助，帮他完成这个问题吧。
输入：
输入包含T组数据。每组数据包含两行，第一行包含两个整数n和m，代表一个数的位数和要删除的位数个数;第二行为一个n位的整数;（0<=m<n<5000)
输出：
每组数据输出一行，表示删除后能够构成的最小整数
示例输入：
2
5 2
54321
5 4
42130示例输出：
123
0
提示：
参考答案（内存最优[1120]）：
#include<stdio.h>
#include<math.h>
#include<string.h>
int main()
{
int i,t;
int n;
int j,k;
int te;
int a[5005];
char b[5005];
int sum=0,mi;
scanf("%d",&n);
int x=0;
while(n--)
{
x=0;
mi=99;
sum=0;
scanf("%d%d",&j,&k);
scanf("%s",b);
for(i=0;i<j;i++)
{
a[i]=b[i]-'0';
if(a[i]==0)
sum++;
if(a[i]<mi&&a[i]!=0)
mi=a[i];
}
for(i=0;i<j;i++)
for(t=0;t<j-1;t++)
{
if(a[t]>a[t+1])
{
te=a[t];
a[t]=a[t+1];
a[t+1]=te;
}
}
if(sum>=j-k)
printf("0");
else
{
printf("%d",mi);
for(i=0;i<=j-k-1;i++)
{
if(a[i]==mi&&x==0)
{
x++;
continue;
}
printf("%d",a[i]);
}
}
printf("\n");
}
}
参考答案（时间最优[0]）：
#include <iostream>
#include<stdlib.h>
#include<stdio.h>
#include<memory.h>
using namespace std;
char c[5001];
int cmp(const void *a,const void *b)
{
return *(char *)b-*(char *)a;
}
int check(int n,int m)
{
int i;
for(i=n-1; i>=m; i--)
{
if(c[i]!='0')
return 0;
}
return 1;
}
int fin(int n,int m)
{
int i;
for(i=n-1; i>=m; i--)
{
if(c[i]!='0')
return i;
}
return 0;
}
int main()
{
char s[5001];
int n,m,t,i,k,z;
//freopen("g:\\TDDOWNLOAD\\test0.in","r",stdin);
//freopen("g:\\output02.txt","w",stdout);
while(cin>>t)
{
while(t--)
{
memset(c,'\0',sizeof(c));
memset(s,'\0',sizeof(s));
cin>>n>>m;
//getchar();
//cin>>c;
//getchar();
//gets(c);
//gets(c);
scanf("%s",c);
qsort(c,n,sizeof(c[0]),cmp);
if(c[n-1]!='0')
{
for(i=n-1; i>=m; i--)
cout<<c[i];
cout<<endl;
}
else if(c[n-1]=='0'&&!check(n,m))
{
k=fin(n,m);
s[0]=c[k];
for(i=n-1,z=1; i>=m; i--)
{
if(i!=k)
s[z++]=c[i];
}
cout<<s<<endl;
}
else if(check(n,m))
cout<<"0"<<endl;
}
}
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。