老大的烦恼

老大的烦恼

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注