一、写在前面

这道题目深刻地告诉了自己基础的重要性！！！

读完题目直接想到打表，然后因为是有序数组，所以直接想到二分。到这里按说这道题应该很好做，但是自己首先，忘了lower_bound和upper_bound的区别，然后去查区别，浪费了时间。然后又因为其它地方的错误，交上去WA了，自己又以为是二分没写好，于是把二分改成了手写二分，结果手写二分又忘了怎么写，于是去查手写二分，又浪费了时间，而且交上去还是WA.

然后仔细读代码后发现，打表时少打了一位，应该打到1e9-1，而自己只打到了1e8-1，这时已经浪费了很多时间了，匆匆忙忙改了之后，又WA了。这时摆在自己面前的有两个选择，一是把二分改成枚举，因为这时候自己发现其实表里面没几个数，完全可以改；另一个选择是继续debug当前的代码。然而这个时候已经是深夜，第二天还要准备期中考试，所以当时自己也不想继续做后面的题了，就想把这道题的二分方法改好，但是直到比赛结束也还是过不了第四个样例。

第二天比赛彻底结束后，自己看了一下没有过的样例，发现第当n=1e9 ，和n=999999999（九个9）的时候，都莫名其妙地输出了82，而正确答案是81.检查发现表是对的，那么问题出现在二分上，直觉告诉我再在后面补一个数1e9+1就对了，交上去果然AC，但是二分为什么会出错呢？

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 vector<int> w;
 8 int s[10];
 9 void pre_work(){
10     for(int i=1;i<=9;i++){                        
11         for(int j=1;j<=9;j++){
12             s[j]=s[j]*10+j;
13             w.push_back(s[j]);
14         }
15     }
16     w.push_back(1000000001);                     //加了这一步就对了
17 }
18 int n;
19 int main(){
20     
21     pre_work();
22     int T;
23     cin>>T;
24     while(T--){
25         scanf("%d",&n);
26         int l=0,r=w.size();
27         while(l<r){
28             int mid=l+r+1>>1;
29             if(w[mid]<=n) l=mid;
30             else r=mid-1;
31         }
32         printf("%d\n",l+1);
33     }
34     
35     //int len=w.size();
36     //for(int i=0;i<len;i++) cout<<w[i]<<endl;
37     //cout<<len<<endl;
38     
39     return 0;
40     
41 }

仔细再看了一遍二分的代码，发现右界写错了。对于这种vector的数组一定要注意下标！！！

正确代码如下

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<vector>
 6 using namespace std;
 7 vector<int> w;
 8 int s[10];
 9 void pre_work(){
10     for(int i=1;i<=9;i++){                        
11         for(int j=1;j<=9;j++){
12             s[j]=s[j]*10+j;
13             w.push_back(s[j]);
14         }
15     }
16 }
17 int n;
18 int main(){
19     
20     pre_work();
21     int T;
22     cin>>T;
23     while(T--){
24         scanf("%d",&n);
25         int l=0,r=w.size()-1;
26         while(l<r){
27             int mid=l+r+1>>1;
28             if(w[mid]<=n) l=mid;
29             else r=mid-1;
30         }
31         printf("%d\n",l+1);
32     }
33     
34     return 0;
35     
36 }

 

二、算法分析

一种思路是打表，然后对于每次的n，可以枚举找n的位置，或者二分来找。

另一种思路从分析的角度出发，可以参考codeforces的官方题解https://codeforces.com/blog/entry/90342