时间复杂度分析

设主动截面长度为 ( n )，从动截面长度为 ( m )。

• 外层循环：枚举主动截面的每个起始位置（共 ( n ) 次）。
• 内层循环：每次循环中，两个指针 ( b ) 和 ( t ) 分别遍历主动和从动截面的重叠部分，最坏情况下每个字符最多被访问一次。
• 总时间复杂度为 ( O(n + m) \times O(\max(n, m)) = O((n + m) \cdot \max(n, m)) )。由于 ( n, m \leq 100 )，实际运行效率很高。

解题思路

问题核心

两个截面沿长度方向平移时，重叠部分中不能同时出现下方的齿（2）和上方的齿（2）（即任意重叠位置的字符之和不能超过 3，因为 2+2=4 > 3，而 1+2=3、2+1=3、1+1=2 均合法）。需找到所有合法平移方式中，两个截面覆盖的最小总长度。

关键步骤

1. 双向平移模拟：

   • 分别考虑主动截面在左、从动截面在右的平移（length(bot, top)），以及从动截面在左、主动截面在右的平移（length(top, bot)），取两者的最小值。

2. 计算重叠长度：

   • 对于主动截面的每个起始位置 ( i )（即主动截面从第 ( i ) 个字符开始与从动截面左端对齐），逐字符检查重叠部分是否合法（字符和 ≤ 3）。
   • 当遇到不合法字符或遍历完其中一个截面时，计算当前有效重叠长度 ( L )，则总长度为 ( n + m - L )（总长度减去重叠部分）。
   • 取所有合法情况中的最大重叠长度 ( L_{\text{max}} )，则最小总长度为 ( n + m - L_{\text{max}} )。

C++代码

#include <stdio.h>  
#include <string.h>  
#include <algorithm>  
#include <math.h>  
  
const int maxn = 110;  
const int THREE = 3+'0'+'0';  
char bot[maxn];  
char top[maxn];  
  
int length(char* bot,char* top)  
{  
    int len = strlen(bot);  
    int len1 = strlen(top);  
    int sum = len + len1;  
    for(int i=0; i<len; i++)  
    {  
        char* b = bot+i;  
        char* t = top;  
        while(*b && *t)  
        {  
            if(*b+*t<=THREE){b++;t++;}  
            else break;  
        }  
        if(!*b || !*t)  
        {  
            if(len-i>len1)sum-=len1;  
            else sum-=(len-i);  
            break;  
        }  
    }  
    return sum;  
}  
  
int main()  
{  
    while(~scanf("%s%s",bot,top))  
    {  
        int sum1 = length(bot,top);  
        int sum2 = length(top,bot);  
        printf("%d\n",sum1<sum2?sum1:sum2);  
    }  
    return 0;  
}  
根据代码给出时间复杂度和代码的解题思路