描述
给定一个十进制正整数n(0 < n < 1000000000),每个数位上数字均不为0。n的位数为m。
现在从m位中删除k位(0<k < m),求生成的新整数最小为多少?
例如: n = 9128456, k = 2, 则生成的新整数最小为12456
输入
第一行t, 表示有t组数据;
接下来t行,每一行表示一组测试数据,每组测试数据包含两个数字n, k。
输出
t行,每行一个数字,表示从n中删除k位后得到的最小整数。
样例输入
2
9128456 2
1444 3
样例输出
12456
1
这道题刚开始看时,水感十足,只需要找到所有位数中,前k大的数,删除后输出就行了(哎╮(╯▽╰)╭,被样例坑了…………)
错误代码没什么技术含量,就不用秀了吧~~~
后面才发现:我们可以把每一位数连起来,当成一座山:
上图是数字9128456的山峰图,可以看出前一位是9,后面依次排出来,就可以练成像山峰一样的图案,我们要做的,就是将越靠近原点的山峰给切掉,遇峰即切,切了k次以后,所得的数必为最小的,让我们来看个例子:
124563789 3
先把“6”切掉
再退出循环,重新搜索,切“5”
再切“4”
好了,剩下的数字123789就一定为最小了~\(≧▽≦)/~
不说了,丢代码:
<span style="font-size:14px;">#include<cstdio>
#include<cstring>
int a[31],n,k;
void scan()
{
int i;
char c[31];
scanf("%s%d",c,&k);
n=strlen(c);
for(i=0;i<n;i++)
a[i+1]=c[i]-48;
}
void del(int x)
{
int i;
for(i=x;i<=n;i++)//将切掉的地方缝起来
a[i]=a[i+1];
n--;//总长度减一
}
void work()//切山
{
int i,j;
for(i=1;i<=k;i++)
for(j=1;j<=n;j++)
if(a[j]>a[j+1])//判断是否是山峰
{
del(j);//切掉
break;
}
}
void print()
{
int i;
for(i=1;i<=n;i++)
printf("%d",a[i]);
printf("\n");
}
void over(){memset(a,0,sizeof(a));}//多组数据初始化
int main()
{
int nn;
scanf("%d",&nn);
for(;nn;nn--)
{
scan();
work();
print();
over();
}
}</span>
可以,很贪心