CodeForces 387C – George and Number [贪心]

点击打开Codeforces题目链接

题意

一个数列,可以任选两个数字,大数在前小数在手合并后放在数列最后,然后删除这两个数字。经过若干次操作后数列变成一个数。给你这样的最后的数,问你初始数列最多可能有多少个数字

分析

倒着想这个数的形成过程。逐步从后往前贪心即可,符合条件就拿出来作为那个小的数字

C++代码

#include <bits/stdc++.h>
using namespace std;

string num;

int cmp(int l, int r) {
    if(r - l < l) return true;
    if(r - l > l) return false;
    return num.substr(0, l) >= num.substr(l, r-l);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin >> num;
    int cnt = 0;
    for(int i = num.size()-1, R = num.size(); i >= 0; --i) {
        if(num[i]=='0') continue;
        if(i == 0 || cmp(i, R)) {
            cnt += 1;
            R = i;
        }
    }
    cout << cnt << endl;
    return 0;
}

欢迎留言