首页 › 题库 › C/C++编程考级 › C/C++编程五级 › 简答题
简答题 偏难
#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&lt;bits/stdc++.h&gt; using namespace std; #define N 15 int main() {     int k, t;      char s[N], a[N];     cin &gt;&gt; t;     while(t--)     {         cin &gt;&gt; s &gt;&gt; k;         int an = 0, len = strlen(s), i = 0;         while(i &lt; len)         {             if(k == len-i)//如果剩下的元素个数只有k个,那么都删掉                  break;             int mi = i;//求i~i+k的最小值下标              for(int j = i; j &lt;= i+k; ++j)             {                 if(s[j] &lt; 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 &lt;= an; ++i)             cout &lt;&lt; a[i];         cout &lt;&lt; endl;     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法2:删掉比后面数字大的数字 #include&lt;bits/stdc++.h&gt; using namespace std; #define N 15 int main() {     int k, t;      char s[N], a[N];     cin &gt;&gt; t;     while(t--)     {         cin &gt;&gt; s &gt;&gt; k;         int an = 0, len = strlen(s), ct = 0;         for(int i = 0; i &lt; len; ++i)         {             while(an &gt; 0 &amp;&amp; a[an] &gt; s[i] &amp;&amp; ct &lt; k)//a[an]为前一个数 s[i]为后一个数,当a[an]&gt;s[i]时,删除a[an]             {                 an--;                 ct++;//删除数字个数加1             }             a[++an] = s[i];//无论如何s[i]都会填充进数组a         }         while(ct &lt; k)//删除末尾的k-ct个元素         {             an--;             ct++;         }             for(int i = 1; i &lt;= an; ++i)             cout &lt;&lt; a[i];         cout &lt;&lt; endl;     }     return 0; }</pre><pre class="brush:cpp;toolbar:false">//解法3: #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;cstdlib&gt; #include&lt;cstring&gt; #include&lt;algorithm&gt; #define INF 999999999 #define N 101 using namespace std; char str[N]; int main() {     int t,n;     cin&gt;&gt;t;     while(t--)     {         cin&gt;&gt;str&gt;&gt;n;         int len=strlen(str);         while(n--)         {             for(int i=0;i&lt;len-1;i++)                 if(str[i]&gt;str[i+1])                 {                     for(int j=i;j&lt;len-1;j++)                         str[j]=str[j+1];                     break;                 }             len--;         }         str[len]='\0';         cout&lt;&lt;str&lt;&lt;endl;     }     return 0; }</pre><p><br/></p>
这道题暂未补解析。