cf C. George and Number

http://codeforces.com/problemset/problem/387/C

题意：给你一个大数，让你求个集合，可以通过操作得到这个数，求集合中个数最大值，操作：从集合中任意取两个数，大的数放在前面小的数放在后面组成一个数在重新放入集合中，经过重复的操作，集合中只剩一个数，这个数就是给你的数。

思路：要求个数最大，可以让这个大数的每一个数字为集合中的一个数，但是集合中不能有0，所以在连续的0前面要连着一个非零的数。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 char str[1000000];
 7 
 8 int main()
 9 {
10     while(scanf("%s",str)!=EOF)
11     {
12         int k=strlen(str);
13         int ans=0;
14         for(int i=k-1; i>=0; i--)
15         {
16              int j=i;
17              while(str[i]=='0') i--;
18              if(j-i+1<i) ans++;
19              else if(j-i+1==i)
20              {
21                  bool flag=false;
22                  for(int k=0; k<i; k++)
23                  {
24                      if(str[k]>str[k+i]&&str[k]!=str[k+i])
25                      {
26                          flag=true;
27                          ans++;
28                          break;
29                      }
30                      else if(str[k]<str[k+i]&&str[k]!=str[k+i])
31                      {
32                           ans++;
33                           i=0;
34                           flag=true;
35                           break;
36                      }
37                  }
38                  if(!flag) ans++;
39              }
40              else if(j-i+1>i)
41              {
42                  i=0;
43                  ans++;
44              }
45         }
46         printf("%d
",ans);
47     }
48     return 0;
49 }

View Code