POJ 1496 Word Index map超时分析-白红宇

POJ 1496 Word Index map超时分析

阅读量：5020 次

发布时间：2019-06-12

本文共 1816 字，大约阅读时间需要 6 分钟。

题意：

大约是就按照下面的方式给字符串编号，然后给你一个字符串让你输出它的编号。

a -> 1

b -> 2

. .

z -> 26

ab -> 27

ac -> 28

. .

az -> 51

bc -> 52

. .

vwxyz -> 83681

解法：

没有想到很好的解法，所以就枚举了。因为解的范围并不大，最多83681。而且每一步的代价并不大：3个步骤：保存结果，自加，进位。

发现问题：

保存结果很自然想到的是用map<string,int>，因为这样的话就可以在O(lg(n))的复杂度下找到结果。但是，这样做的结果超时了。后来改成保存在数组里，这样查找一个结果的话，复杂度是O（n），但是，这样反而0ms通过了。

问题解析：

想了很久没想通就是因为我们只注意了查找结果的过程，而忽略了生成结果的过程。在生成结果的时候我们要把83681个结果放到中，map插入的效率是O（lg（n）），而保存到数组中只需要直接拷贝，复杂度是O（l）。在这一点上数组是优于map的。但是lg（83681）<17，17倍的差距好像不太会导致超时。进一步分析，我们会发现，其实我们生成的字符串是有规律的，他们大多数时候是按字典序递增的，而我们又知道map是用红黑树来实现的，当你的输入是一个有序的序列时候，为了使树的形态保持平衡，他会对树进行重新上色，左旋，右旋等操作，来调整树的高度。所以，我们在插入这些字符串的时候，map就在不断进行着调整。虽然这个算法的阶还是O（lg（n）），但是这其中其实隐含了更大的常数因子。所以，这就是为什么map，输给了数组。

下面附上ac代码：

//POJ 1496 Word Index#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          using namespace std;//map
           
             ans;char answer[83682][6];void MakeAns(){ char word[7]; int start = 5,i; memset(word,'a'-1,sizeof(word)); word[6] = 'z'+1; word[5] = 'a'; for(int no = 1; no <= 83681;no++) { i = 0; for(int j = start; j < 6; j++) answer[no][i++] = word[j]; answer[no][i] = 0; /* string s(word+start,word+6); ans[s] = no;*/ word[5]++; for( i = 5; i > 0 && word[i] >= word[i+1]; i--) { word[i]--; word[i-1]++; } for( ;i + 1 < 6; i++) { if( i < start ) { start = i; } word[i+1] = word[i] + 1; } }}bool check(char str[]){ for(int i = 1; str[i]; i++) { if(str[i] <= str[i-1] ) return false; } return true;}int search(char str[]){ for(int i = 1; i <= 83681; i++) { if(strcmp(str,answer[i]) == 0) return i; } return 0;}int main(){ MakeAns(); char str[10]; while(scanf("%s",str)!=EOF) { if(!check(str)) printf("0\n"); else printf("%d\n",search(str)); } return 0;}

转载于:https://www.cnblogs.com/illuminator/archive/2013/03/22/POJ1496.html

你可能感兴趣的文章