hdu 5578 Friendship of Frog

题意：给定一行字符串(都是小写字母)，每一个字符都代表一只青蛙以及其国籍，若字符串中出现两个字符相同，则这两个字符所代表的青蛙来自同一国度，可称之为好朋友。

现在需要找到距离最近的好朋友并输出他们的距离。

思路：建立一个map映射表，映射关系为：字符<->字符所在字符串的位置，从字符串头部到尾部依次进行扫描，每扫到一个字符，可以找一找map表中有没有出现该字符，若没出现过则在

表中建立这个字符的关系，若map表中有该字符的记录，那么说明当前字符串代表的青蛙找到了一个朋友，可以计算他与朋友的距离，并更新最短距离。之后map表也要更新这个字符的信息，

即把字符所在位置改为当前位置以方便后续的操作。

AC代码：

#define _CRT_SECURE_NO_DEPRECATE

#include<iostream>

#include<algorithm>

#include<string>

#include<set>

#include<map>

using namespace std;

string s;

map<char, int>m;//coutry<->position

int main() {

    int T;

    scanf("%d",&T);

    int k = ;

    while (T--) {

        k++;

        cin >> s;

        int dis = INT_MAX;

        m.clear();//每次用完需要清空map表

        for (int i = ; i < s.size(); i++) {

            map<char,int>::iterator it = m.find(s[i]);

            if (it != m.end()) {//集合中找到了这只青蛙的同伴

                int distance = i - it->second;

                if (distance < dis)dis = distance;

                m.erase(s[i]);//更新青蛙位置

                m.insert(make_pair(s[i], i));

              }

            else {

                m.insert(make_pair(s[i],i));//新元素，记录位置

            }

        }

        if (dis >= s.size())

            printf("Case #%d: -1\n", k);

        else

            printf("Case #%d: %d\n",k,dis);

    }

    return ;

}

巴特西

hdu 5578 Friendship of Frog

最新文章

热门文章