bupt|127. 最小距离查询

小灰灰 2023-05-21 10:22 16阅读 0赞

[http://10.105.242.83/problem/127/][http_10.105.242.83_problem_127]

**题目描述:**

给定一个由小写字母a到z组成的字符串S ,其中第i个字符为S\[i\] (下标从0开始) .你需要完成下面两个操作:  
INSERT c  
其中c是一一个待输入的字符。你需要在字符串的末尾添加这个字符。保证输入的字符同样是a到z之间的一一个小写字母.  
QUERY x  
其中x是一个输入的整数下标。对于这个询问,你需要回答在S当中和S\[x\]相等且与x最近的距离。输入保证x在当前字符串中合法。 例如S = “abcaba” ,如果我们操作: INSERT a 则在S的末端加一个字符a , S变成abcabaa".  
接下来操作 QUERY 0  
由于S\[0\]=a ,在S中出现的离他最近的a在下标为3的位置上,距离为3-0=3.因此应当输出3.  
接下来,如果 QUERY 4  
S\[4\]=b, S中离它最近的b出现在下标为1处,距离为4- 1=3.同样应当输出3. 给定初始字符串S和若干操作,对于每个QUERY，你需要求出相应的距离。 HINT由于输入数据较大, C/C++中推荐使用scanf进行读入以获得更快的读入速度。同时请注意算法复杂度。

**输入格式:**

输入的第一行是一一个正整数T(T < 20) ,表示测试数据的组数。 每组输入数据的第一行是-一个初始串S。第二行是一一个正整数  
m(1≤m≤100000),表示总共操作的数量。接下来m行，每行表示一个操作。操作的格式如上所述。  
数据保证在任何情况下，S的长度不会超过100000.

**输出格式:**

对于每个QUERY ,输出所求的最小距离。如果S中其它位置都不存在和它相同的字符,输出-1。

2
    axb
    3
    INSERT a
    QUERY 0
    QUERY 1
    explore
    3
    INSERT r
    QUERY 7
    QUERY 1

输出样例:

3
    -1
    2
    -1

#include<bits/stdc++.h>
    using namespace std;
    int main() { 
        int T, m, x;
        scanf("%d", &T);
        while(T--) { 
            char s[100005];
            vector<vector<char> > p(26);
            memset(s, 0, sizeof(s));
            scanf("%s", s);
            int len = strlen(s);
            for(int i = 0; i < len; i++) {  //统计字母个数
                p[s[i] - 'a'].push_back(i);
            }
            scanf("%d", &m);
            for(int i = 0; i < m; i++) { 
                char tmp[20];//操作
                scanf("%s\n", tmp); //读取空格
                if(strcmp(tmp, "INSERT") == 0) { 
                    char ch;
                    scanf("%c", &ch);
                    s[len] = ch;
                    s[len + 1] = '\0'; //补充完整字符串
                    p[ch - 'a'].push_back(len);
                    len = len + 1;
                } else if(strcmp(tmp, "QUERY") == 0) { 
                    scanf("%d", &x);
                    if(p[s[x] - 'a'].size() == 1) { 
                        printf("-1\n");
                    } else {  //找最小距离
                        int min_value = 0x3f3f3f3f;
                        for(int k = 0; k < p[s[x] - 'a'].size(); k++) { 
                            if(abs(p[s[x] - 'a'][k] - x) < min_value && abs(p[s[x] - 'a'][k] - x) != 0)
                                min_value = abs(p[s[x] - 'a'][k] - x);
                        }
                        printf("%d\n", min_value);
                    }
                }
            }
        }
        return 0;
    }

[http_10.105.242.83_problem_127]: http://10.105.242.83/problem/127/