Posted on 2011-05-11 23:38
acpeng 閱讀(697)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
ACM程序
昨天逛一論壇，遇到一道
acm題，地址是
http://acmpj.zstu.edu.cn/JudgeOnline/showproblem?problem_id=2511大致意思是從一個(gè)有
n 位的整數(shù)中刪除
k 位，使剩下的數(shù)字按原來的順序組成的數(shù)最小。
我的代碼總是
WA，不知有沒有大牛路過，指點(diǎn)一二，在此謝。
我的思路是這樣：
步驟一：在第 1 位到第
k+1 位之間（含第
k+1 位）找出最小的數(shù)字，記錄這個(gè)數(shù)字所在的位數(shù)p；
步驟二：再從第
p 位到第
k+2 位之間找出最小的數(shù)字，再記錄此數(shù)所在的位數(shù)p；
后面重復(fù)
n-k 次前面的操作，這樣按順序輸出每一次操作得到的最小數(shù)字即可。當(dāng)然輸出時(shí)注意去掉起始的若干個(gè)0。
下面是代碼
#include<stdio.h>
#include<string.h>
char a[1005]="\0",rslt[1005]="\0";
int main()
{
int T,k,n,i,j,lp;
scanf("%d",&T);
while(T--)
{
scanf("%d",&k);
scanf("%s",a);
n=(int)strlen(a);
if(k==n)
{
printf("0\n");
continue;
}
lp=-1;
for(j=0;j<n-k;j++)
{
lp++;
rslt[j]=a[lp];
for(i=lp;i<k+j+1;i++)
{
if(rslt[j] > a[i])
{
rslt[j]=a[i];
lp=i;
}
}
}
i=0;
while(*(rslt+i)=='0' && *(rslt+i)!='\0') i++;
printf("%s\n",rslt+i);
memset(a,0,sizeof(a));
memset(rslt,0,sizeof(rslt));
}
return 0;
}