CodeForces 387 C. George and Number[貪心]

題目連結：點選打開連結

C. George and Number time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output

George is a cat, so he really likes to play. Most of all he likes to play with his array of positive integersb. During the game, George modifies the array by using special changes. Let's mark George's current array asb1, b2, ..., b|b| (record|b| denotes the current length of the array). Then one change is a sequence of actions:

• Choose two distinct indexes i and j (1 ≤ i, j ≤ |b|; i ≠ j), such thatbi ≥ bj.
• Get number v = concat(bi, bj), whereconcat(x, y) is a number obtained by adding numbery to the end of the decimal record of numberx. For example, concat(500, 10) = 50010,concat(2, 2) = 22.
• Add number v to the end of the array. The length of the array will increase by one.
• Remove from the array numbers with indexes i and j. The length of the array will decrease by two, and elements of the array will become re-numbered from1 to current length of the array.

George played for a long time with his array b and received from array b an array consisting of exactly one numberp. Now George wants to know: what is the maximum number of elements arrayb could contain originally? Help him find this number. Note that originally the array could contain onlypositive integers.

Input

The first line of the input contains a single integerp (1 ≤ p < 10100000). It is guaranteed that numberp doesn't contain any leading zeroes.

Output

Print an integer — the maximum number of elements arrayb could contain originally.

Sample test(s) Input

9555
      

Output

4      

Input

10000000005
      

Output

2      

Input

800101
      

Output

3      

Input

45
      

Output

1      

Input

1000000000000001223300003342220044555
      

Output

17      

Input

19992000
      

Output

1      

Input

310200
      

Output

2      

一開始，了解錯題意了。。以為必須i > j && ai >= aj呢。。。。沒有前面的限制。。。如果有前面的限制。。題目的難度就更高了。。。。

沒有了上面的限制就比較好了解了。。。。水水的貪心。。。

貪心政策：

1.把每位數分開來，需要注意的是0的話，應該歸到他前面非0的數中。。

  比如 100001001000 需要分為10000，100，1000。。

2.第一個數如果>=第二個數，那麼意味這這兩個數原始的時候可以為兩個數。合并。

  否則，這兩個數最開始為1個數。。

Code：

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 1e5 + 5;

bool Judge(string a, string b)
{
    if(a.size() > b.size()) return true;
    else if(a.size() == b.size() && a >= b) return true;
    return false;
}

int main()
{
    string s, s1[N];
    cin >> s;
    int len = s.size(), top = 0;
    for(int i = 0; i < len; i ++){
        string tmp = "";
        tmp += s[i];
        i ++ ;
        for( ; s[i] == '0' && i < len; i ++){
            tmp += s[i];
        }
        i --;
        s1[top ++] = tmp;
    }
    int ans = 1;
    string now = s1[0];
    for(int i = 1; i < top; i ++){
        if(Judge(now, s1[i])) {
            ans ++;
        }
        else ans = 1;
        now += s1[i];
    }
    cout << ans << endl;
    return 0;
}
           

好吧。。又一次被題意給坑了。。