题目链接：点击打开链接
1 second
256 megabytes
standard input
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.
The first line of the input contains a single integerp (1 ≤ p < 10100000). It is guaranteed that numberp
doesn't contain any leading zeroes.
Print an integer — the maximum number of elements arrayb could contain originally.
9555
4
10000000005
2
800101
3
45
1
1000000000000001223300003342220044555
17
19992000
1
310200
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;
}
好吧。。又一次被题意给坑了。。