【CodeForces-258A】Little Elephant and Bits【贪心】

【CodeForces-258A】Little Elephant and Bits【贪心】

问题十分简单,给出一个二进制表示的数,要求去除任意一位后,能够取得的最大值,我们使用字符串来操作,因为相同长度下,较大的数值其字典序一定较大【如果长度不一样则不一定满足,需要注意】,在一般情况下,我们只能够删去一个0或者一个1,如果删去0,则删去从左边开始的第一个0会得到所有删去0的结果的最大值,因为它让其右边的所有位数尽可能的向高位靠拢;类似的,如果删去1,则从最右边开始的第一个1删去,可得到所有删去1的结果中最大的值,之后比较这两个值就可以知道是删除0还是删除1的方案得到的数更大。对于特殊情况【全是0或全是1】,需要加一些特殊处理,让最后生成的字符串长度为n【即出现没有删减的情况】,我们检测到删0或删1方案得到的数没有删减时,就可以确认另一种删的方案一定成功删除了,故直接输出另一种方案即可。

#include <iostream>
#include <algorithm>
#include <string>

using namespace std;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    string str;
    cin >> str;
    int n = str.size();
    string tmp = "", a, b;
    bool flag = true;
    int pos = 0;
    for (int i = 0; i < n; i++) {
        if (flag && str[i] == '0') {
            flag = false;
            continue;
        }
        if (str[i] == '1') pos = i;
        tmp += str[i];
    }
    a = tmp;
    tmp = "";
    for (int i = 0; i < n; i++) {
        if (i == pos && str[i] == '1') continue;
        tmp += str[i];
    }
    b = tmp;
    if (b.size() == n || a.size() != n && a > b)
        cout << a << "\n";
    else
        cout << b << "\n";
    return 0;
}