51nod-1385-贪心-构造

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1385

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

给定一个n,要求找出一个最短的字符串S，使得所有1到n的整数都是S的子序列。

比如n=10，那么S=”1234056789”的时候，是满足条件的。这个时候S的长度是10。

现在给出一个n，要求输出最短S的长度。

Input

第1行：给出一个整数n (1<=n<=1e10000)。

Output

输出最短S的长度

Input示例

Output示例

10
  不难发现最优的方法就是 12345678901234567890123456789......如此往复，关键就是找准每一位最高贡献到那个数字使得1--这个数字全能表示出来，找规律发现就是n个后面那个数字组成的数
再减去一就是这一位能表示到的最大的数。
 n位数一定能表示所有n-1位数，所以ret=(n-2)*10+9;
 再从最高位考虑，只剩下两个数，到s[0]/s[0]+1 ,让N与最后一个循环节循环到到s[0]能表示的极限作比较，如果N更大就ret+=s[0]-'0'+1;否则ret+=s[0]-'0';

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 char s[10015];
 4 int f(){
 5     int n,ret;
 6     cin>>s;
 7     n=strlen(s);
 8     if(n==1){return s[0]-'0';}
 9     ret=(n-2)*10+9+s[0]-'0';
10     for(int i=0;i<n;++i){
11         int r=i==n-1?s[0]-'0'-1:s[0]-'0';
12         if(s[i]-'0'<r){
13                 break;
14         }
15         if(s[i]-'0'>r){
16             ret++;
17             break;
18         }
19     }
20     return ret;
21 }
22 int main(){cout<<f()<<endl;}