本文主要是介绍CodeForces 387C George and Number，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：http://codeforces.com/problemset/problem/387/C
George and Number
George is a cat, so he really likes to play. Most of all he likes to play with his array of positive integers b. During the game, George modifies the array by using special changes. Let's mark George's current array as b1, 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 that bi ≥ bj.
- Get number v = concat(bi, bj), where concat(x, y) is a number obtained by adding number y to the end of the decimal record of number x. 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 from 1 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 number p. Now George wants to know: what is the maximum number of elements array b could contain originally? Help him find this number. Note that originally the array could contain only positive integers.
Input
The first line of the input contains a single integer p (1 ≤ p < 10100000). It is guaranteed that number p doesn't contain any leading zeroes.
Output
Print an integer — the maximum number of elements array b could contain originally.
Sample test(s)
9555
4
10000000005
2
800101
3
45
1
1000000000000001223300003342220044555
17
19992000
1
310200
2
Note
Let's consider the test examples:
- Originally array b can be equal to {5, 9, 5, 5}. The sequence of George's changes could have been: {5, 9, 5, 5} → {5, 5, 95} → {95, 55} → {9555}.
- Originally array b could be equal to {1000000000, 5}. Please note that the array b cannot contain zeros.
- Originally array b could be equal to {800, 10, 1}.
- Originally array b could be equal to {45}. It cannot be equal to {4, 5}, because George can get only array {54} from this array in one operation.
Note that the numbers can be very large.
大意——有一个游戏的规则是这样的：给定一个正整数数组，从数组中选取两个数，将大的放在前面，小的放在后面，然后拼接在一起组成一个数，取代这两个数放在数组中。如果用同一个数组玩很多次时，最后会得到仅仅只有一个数的数组。问：给你最后那一个数，那么它的原数组最大元素数目为多大？给出的数p满足1 ≤ p < 10100000。注意的是，原数组只含有正整数。
思路——这是一道贪心题。数太大，可以用字符数组表示。这样的话，贪心策略是怎样的呢？既然要使得最后元素个数最大，那么我们可以从后面开始找将串分成两个部分的子串，该子串满足：1.前面的串表示的数大于等于该串表示的数；2.该串表示的数要尽量小。找到之后计数一次，接着将前面的串当成新的串继续找，直至不能够找到为止。这样求出的解一定是最优的。
复杂度分析——时间复杂度:O(len),空间复杂度:O(len)
附上AC代码：
#include <iostream>
#include <cstdio>
#include <string>
#include <cmath>
#include <iomanip>
#include <ctime>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <map>
//#pragma comment(linker, "/STACK:102400000, 102400000")
using namespace std;
typedef long long ll;
const double pi = acos(-1.0);
const double e = exp(1.0);
const double eps = 1e-8;
const int maxlen = 100005;
char str[maxlen];bool compare(int x1, int y1, int x2, int y2);
// 比较两个子串表示的数字大小int main()
{ios::sync_with_stdio(false);while (~scanf("%s", str)){int len = strlen(str);int ans=0, end1=len-2, end2=len-1;while (end2 >= 0){while (end1>=0 && (str[end1+1]=='0'||!compare(0, end1, end1+1, end2)))end1--; // 找满足前面大于后面的串if (end1 == -1)break; // 串已经到头了ans++; // 减掉后面的串，数组个数加一end2 = end1; // 重新判断剩下的串end1--;}ans++; // 加上循环结束时那个没计算的子串printf("%d\n", ans);}return 0;
}bool compare(int x1, int y1, int x2, int y2)
{int len1 = y1-x1+1;int len2 = y2-x2+1;if (len1 > len2)return 1;if (len2 > len1)return 0;for (int i=0; i<len1; ++i){if (str[x1+i] > str[x2+i])return 1;else if (str[x1+i] < str[x2+i])return 0;}return 1; // 两个数相等
}
这篇关于CodeForces 387C George and Number的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
