简答题
偏难
#7432
最小新整数 给定一个十进制正整数n(0 < n < 1000000000),每个数位上数字均不为0。n的位数为m。 现在从m位中删除k位(0<k < m),求生…
最小新整数
给定一个十进制正整数n(0 < n < 1000000000),每个数位上数字均不为0。n的位数为m。 现在从m位中删除k位(0<k < m),求生成的新整数最小为多少? 例如: n = 9128456, k = 2, 则生成的新整数最小为12456
时间限制:1000
内存限制:65536
输入
第一行t, 表示有t组数据; 接下来t行,每一行表示一组测试数据,每组测试数据包含两个数字n, k。
输出
t行,每行一个数字,表示从n中删除k位后得到的最小整数。
样例输入
2 9128456 2 1444 3
样例输出
12456 1
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//解法1:每次找k+1个数中的最小值
#include<bits/stdc++.h>
using namespace std;
#define N 15
int main()
{
int k, t;
char s[N], a[N];
cin >> t;
while(t--)
{
cin >> s >> k;
int an = 0, len = strlen(s), i = 0;
while(i < len)
{
if(k == len-i)//如果剩下的元素个数只有k个,那么都删掉
break;
int mi = i;//求i~i+k的最小值下标
for(int j = i; j <= i+k; ++j)
{
if(s[j] < s[mi])
mi = j;
}
a[++an] = s[mi];
k -= mi - i;//s[i]~s[mi-1]都删掉,删掉了mi-i个元素
i = mi + 1;
}
for(i = 1; i <= an; ++i)
cout << a[i];
cout << endl;
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//解法2:删掉比后面数字大的数字
#include<bits/stdc++.h>
using namespace std;
#define N 15
int main()
{
int k, t;
char s[N], a[N];
cin >> t;
while(t--)
{
cin >> s >> k;
int an = 0, len = strlen(s), ct = 0;
for(int i = 0; i < len; ++i)
{
while(an > 0 && a[an] > s[i] && ct < k)//a[an]为前一个数 s[i]为后一个数,当a[an]>s[i]时,删除a[an]
{
an--;
ct++;//删除数字个数加1
}
a[++an] = s[i];//无论如何s[i]都会填充进数组a
}
while(ct < k)//删除末尾的k-ct个元素
{
an--;
ct++;
}
for(int i = 1; i <= an; ++i)
cout << a[i];
cout << endl;
}
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#define INF 999999999
#define N 101
using namespace std;
char str[N];
int main()
{
int t,n;
cin>>t;
while(t--)
{
cin>>str>>n;
int len=strlen(str);
while(n--)
{
for(int i=0;i<len-1;i++)
if(str[i]>str[i+1])
{
for(int j=i;j<len-1;j++)
str[j]=str[j+1];
break;
}
len--;
}
str[len]='\0';
cout<<str<<endl;
}
return 0;
}</pre><p><br/></p>
这道题暂未补解析。