删数问题

佚名 6年前 (2018-10-03) 算法 853人围观抢沙发百度已收录

题目链接

Problem Description
键盘输入一个高精度的正整数n（≤100位），去掉其中任意s个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的n与s，寻找一种方案，使得剩下的数字组成的新数最小。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Input
输入有多组每组包括原始数n，要去掉的数字数s；

Output
输出去掉s个数后最小的数

Sample Input
178543 4

Sample Output
13

思路:

遇到逆序就删除,如果逆序删除完之后还是没有删够,那就删除最后一个数字 n - num 次即可
12548 删除3位数字 -> 1248 -> 124 ->12

AC代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int main(){
 5     int n,num;
 6     string s;
 7     while(cin >> s){
 8         scanf("%d",&n);
 9         if(n >= s.size()){
10             printf("0\n");
11             continue;
12         }
13         else{
14             num = 0;
15             for(int i = 1;i < s.size();i++){
16                 if(s[i - 1] > s[i]){
17                     num++;
18                     s.erase(i - 1,1);
19                     if(num == n)
20                         break;
21                     //由于删除完之后下标不会往前移动,且循环要加1，所以要想回到原来的位置共需要减2
22                     i = i - 2;
23                 }
24             }
25             if(num != n)
26                 for(int i = 0;i < n - num;i++)//删除最后一个,删除n - num次即可
27                     s.erase(s.size() - 1);
28             for(int i = 0;i < s.size();i++){
29                 if(s[i] != '0'){
30                     for(int j = i;j < s.size();j++)
31                         cout << s[j];
32                     printf("\n");
33                     break;
34                 }
35                 if(i == s.size() - 1){//如果最后全部都是0,那么只要输出0即可
36                     printf("0\n");
37                     break;
38                 }
39             }
40         }
41     }
42     return 0;
43 }