Uva 11419 遇黑则白，反向思考

一、题意

输入n、d（d<n<100000）。
然后输入一个n位的数字，要求你从中删去d个，使得剩下的数字最大。

二、解析

先给出我一开始想的一种错误的思路：即每次都删去最小的、位置靠前的数字。
这个乍看一下很有道理，但实际上是错误的，因为这个没有从全局考虑。比如一个231这个3位数字，只能删去一个，则显然我们要删除的是2而不是1。

通过上面这个例子我们也能发现，实际上真正的贪心思路应该是反过来想的，即每次从开头找一个最大的数字进行保留。这样对于231，由于我们最终要保留2个数字，因此我们逐个挑选，先选出最大的3，然后再选择1。

于是我们就可以用O(n)时间从头到尾扫一遍，每次在一个区间段中找一个最大值进行保留，那这个区间段如何确定呢？这个区间段只需要满足能在后面余留充足的数字个数以便进行后续的挑选即可。

三、代码

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int n, d;

int main() {
    while(cin >> n >> d && n) {
        string str;
        cin >> str;
        int num = n - d;
        auto idx = str.begin();
        while(num) {
            if(idx + num == str.end()) {
                cout << str.substr(idx - str.begin());
                break;
            }
            auto iter = max_element(idx, str.end() - (num - 1));
            cout << *iter;
            idx = iter + 1, num --;
        }
        cout << endl;
    }
}

四、归纳

• 遇黑则白的思想：当题目要求挑选一些元素进行删除时，也许可以考虑考虑反过来思考，即挑选一部分元素进行保留的操作。
• C++的algorithm库可以方便的找最值：即 max_element(begin, end, cmp) 和 min_element(begin, end, cmp) 函数，返回值为迭代器。十分方便。