1321：【例6.3】删數問題(Noip1994)——貪心

【題目描述】

輸入一個高精度的正整數n，去掉其中任意s個數字後剩下的數字按原左右次序組成一個新的正整數。程式設計對給定的n和s，尋找一種方案使得剩下的數字組成的新數最小。

輸出新的正整數。（n不超過240位）

輸入資料均不需判錯。

【輸入】

n

s

【輸出】

最後剩下的最小數。

【輸入樣例】

175438

4

【輸出樣例】

13

分析

1. 首先找貪心的政策：

• 一開始想着直接冒個泡排序，删n個數，這是不對的，因為題目說按原左右次序組成一個新的正整數；
• 其次想到删除序列中最大的數這種政策，這種也是不正确的；（eg：658删除1位，如果僅考慮删除最大數，那麼變成65，這顯然不是最優解，最優為删6，變58； ）

• 正确政策：删除目前數大于後一個數的數，如果s[j] > s[j + 1]，那就把s[j]删掉，以題目樣例示範

  175438

  4

  7>5，删掉7，然後再從頭找；5>4，删掉5，然後再從頭找；；4>3，删除4，然後再從頭找，發現沒有能删除的，已經是一個單調遞增序列，陷入n>0沒删夠的死循環，一直也找不到s[j] > s[j + 1]，直接break（通過一個flag打标記）

1. 單調序列，直接删除最後一個就是最優的，比如123,148…
2. 最後輸出要注意前導0問題，比如某個序列删除後為0041，删除後他是夠4位的（不要認為前導0自己去掉，相當于多删除了兩位變成41）；用一個flag，因為s[i]要麼為0，要麼不為0，非0的話，直接flag=1，已有非零數當第一位，後面的0可以放心輸出了；
3. 貪心不能隻考慮樣例，想到一種政策，要多列幾組有特點的樣例，驗證目前政策是否完善；
4. 此題沒挖坑（洛谷最後一個測試點就是卡輸出0），可能會出現删完最後就剩下一個0，就不能當做前導0不輸出了，是以需要特判下；

總結一下：此題的貪心政策就是每次從頭往後找，找第一個 目前數>下一個數，把其删除，然後最後沒删夠n位，那麼剩下的序列就是就是單調增序列，直接删最後一位即可，最後注意前導0輸出問題即可解決；

#include<bits/stdc++.h>

using namespace std;

string s;
int n;

int main() {
    cin >> s >> n;
    while (n) {
        int flag=0;
        for (int j = 0; j < s.size() - 1; ++j) {
            if (s[j] > s[j + 1]) {
                //目前位大于下一位，要删除
                s.erase(j, 1);
                n--;
                flag=1;
                break;
            }
        }
        //說明上面找删除位，找一圈了還沒找到，是以序列為遞增序列，那就死循環了，一直也找不到s[j] > s[j + 1]，直接break
            if (!flag)
                break;
            /*這樣判斷不對，會造成，12341删除2位，造成最後把1删了，而不是3
           if (i == n.size() - 1)
               break;*/
    }
    //說明剩下的都是單調遞增序列，直接删除最後一個，剩幾個沒删删幾個
    while (n--)
        s.pop_back();
    //可能最後就剩個0了，就不能通過下面的方法（特判）
    if(s.size()==1){
        cout<<s;
        return 0;
    }
    int flag = 0;
    for (int i = 0; i < s.size(); i++) {
        //前導0雖然當做一位，但不能輸出
        if (s[i] != '0')//已有非零數當第一位，後面的0可以放心輸出了
            flag = 1;
        if (flag)
            cout << s[i];
    }
    return 0;
}