Posted on 2012-08-10 11:44
hoshelly 閱讀(1078)
評論(0) 編輯 收藏 引用 所屬分類:
Programming
刪數(shù)問題
時間限制：1000 ms | 內(nèi)存限制：65535 KB
描述
給出一個N位正整數(shù)（首位不為0），去掉其中S個數(shù)字后剩下的數(shù)字按左右次序組成一個新的N-S位正整數(shù)（首位不能為0）。對給定的N和S，尋找一種刪數(shù)規(guī)則使得剩下得數(shù)字組成的新數(shù)最小。
輸入
第一行一個正整數(shù)T ,表示有T組測試數(shù)據(jù)。
對于每組測試數(shù)據(jù)：第一行兩個正整數(shù) n ，s （s< n <= 10, 000） (用空格隔開); 第二行為一個n 位正整數(shù)。
輸出
對于每組測試數(shù)據(jù)輸出一行：最小的新數(shù)。
樣例輸入
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;
}