天之道

享受编程的乐趣。
posts - 118, comments - 7, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

删数问题

Posted on 2012-08-10 11:44 hoshelly 阅读(1045) 评论(0)  编辑 收藏 引用 所属分类: Programming
删数问题
时间限制:1000 ms  |  内存限制:65535 KB
描述

           给出一个N位正整数(首位不为0),去掉其中S个数字后剩下的数字按左右次序组成一个新的N-S位正整数(首位不能为0)。对给定的N和S,寻找一种删数规则使得剩下得数字组成的新数最小。

输入
         第一行一个正整数T ,表示有T组测试数据。

        对于每组测试数据:第一行两个正整数 n ,s (s<  n <= 10, 000) (用空格隔开); 第二行为一个n 位正整数。

输出
         对于每组测试数据输出一行:最小的新数。

样例输入
2
10 2
1234334789
11 3
90019008798
样例输出
12333478
19008798

代码:

#include<stdio.h>
int main()
{
    int t,n,s,i,j,c=0;
    char str[1200];
    char *p,*sp;
    scanf("%d",&t);
    while(t--)
    {
        i=0;
        scanf("%d%d",&n,&s);
        scanf("%s",str);
        p=&str[0];
        sp=&str[1];
        while(*sp !='\0')
        {
            if(str[0] =='0')
            {
                for(j=0;j<n-c;j++)
                {
                   str[j]=str[j+1];
                }
                c++;
            }
            if(*p == str[0] && *p > *sp)
            {
                for(j=0;j<n-c;j++)
                {
                   str[j]=str[j+1];
                }
                i++;
                p++;
                sp++;
                continue;
            }
            for(;*p > *sp;*p--,*sp--)
            {
                if(c != s)
                {
                  for(j=i;j<n-c;j++)
                  {
                     str[j]=str[j+1];
                  }
                  i--;
                  c++;
                }
            }
          if(c != s && str[0] !='0')
          {
            p++;
            sp++;
            i++;
          }
           if(c == s)
           {
               break;
           }
        }

        for(i=0;i<n-s;i++)
        {
            printf("%c",str[i]);
        }
        printf("\n");
    }

    return 0;
}

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理