删数问题

link: SDUT-2072

Description:
键盘输入一个高精度的正整数n（≤100位），去掉其中任意s个数字后剩下的数字按照原来的左右次序组成一个新的正整数。编程对给定的n与s，寻找一种方案，使得剩下的数字组成的新数最小。
Input
输入有多组 每组包括原始数n，要去掉的数字数s；
Output
输出去掉s个数后最小的数
Sample Input
178543 4
Sample Output
13
Intentional analysis:
We'd better use the string type to input.What we should do if find a number in the input which is bigger than it's next.Like a[i]>a[i+1].And then delete the a[i].There is the greedy.There are many special situations we shoule consider.

  1. Can't find a a[i] which is satisfy a[i]>a[i+1],just output the first n characters
  2. The answer string s has '0' at the first,the ordering output should be a number,nao a string.So the front '0' is not allowed.
Click to see Chinese Intentional analysis 我们输入的应该是字符串，方便操作并且保证数据范围。为了得到消去之后最大的值，我们只需要找到a[i]>a[i+1]的i并将之删除即可。这就是体现贪心的地方。但是我们还需要考虑一些特殊情况 1. 数本身就是递增的，此时我们只需要输出前n位即可。 2. 得到的答案字符串的前面有0，判断一下并消去即可。

Code:

#include<iostream>
using namespace std;
int main()
{
    string s;
    int n;
    while(cin>>s>>n)
    {
        int l=s.size();
        while(n--)
        {
            for(int i=0;i<l;i++)
            {
                if(s[i]>s[i+1]||i==l-1)
                {
                    s.erase(i,1);
                    break;
                }
            }
        }
        while(s[0]=='0'&&s[1])
            s.erase(0,1);
        cout<<s<<endl;
    }
    return 0;
}
赏