hdu 5578 Friendship of Frog(multiset的应用)

时间：2024-06-04 13:33:44
Problem Description
N frogs from different countries are standing in a line. Each country is represented by a lowercase letter. The distance between adjacent frogs (e.g. the 1st and the2nd frog, the N−1th and the Nth frog, etc) are exactly . Two frogs are friends if they come from the same country.

The closest friends are a pair of friends with the minimum distance. Help us find that distance.
Input
First line contains an integer T, which indicates the number of test cases.

Every test case only contains a string with length N, and the ith character of the string indicates the country of ith frogs.

⋅ ≤T≤.

⋅ for % data, ≤N≤.

⋅ for % data, ≤N≤.

⋅ the string only contains lowercase letters.
Output
For every test case, you should output "Case #x: y", where x indicates the case number and counts from  and y is the result. If there are no frogs in same country, output − instead.
Sample Input
abcecba

abc
Sample Output
Case #:

Case #: -
Source

multiset随便搞搞就出来了。

 #pragma comment(linker, "/STACK:1024000000,1024000000")

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<cmath>

 #include<math.h>

 #include<algorithm>

 #include<queue>

 #include<set>

 #include<bitset>

 #include<map>

 #include<vector>

 #include<stdlib.h>

 #include <stack>

 using namespace std;

 #define PI acos(-1.0)

 #define max(a,b) (a) > (b) ? (a) : (b)

 #define min(a,b) (a) < (b) ? (a) : (b)

 #define ll long long

 #define eps 1e-10

 #define MOD 1000000007

 #define N 1006

 #define inf 1e12

 multiset<int>ms[N];

 multiset<int>::iterator it,it1,it2;

 char s[N];

 int main()

 {

    int t;

    int ac=;

    scanf("%d",&t);

    while(t--){

       for(int i=;i<N;i++){

          ms[i].clear();

       }

       scanf("%s",s);

       int len=strlen(s);

       for(int i=;i<len;i++){

          int u=s[i]-'a';

          ms[u].insert(i);

       }

       int ans=;

       for(int i=;i<;i++){

          //it=ms[i].begin();

          int minnn=;

          int size_=ms[i].size();

          int num=;

          for(it1=ms[i].begin();it1!=ms[i].end();it1++){

             if(size_==){

                break;

             }

             if(num>=size_-){

                break;

             }

             //printf("%d= %d\n",i,(*it1));

             num++;

             it2=it1;

             it2++;

             int dis=(*it2)-(*it1);

             if(dis<minnn){

                minnn=dis;

             }

          }

          //printf("minnn = %d\n",minnn);

          ans=min(ans,minnn);

       }

       printf("Case #%d: ",++ac);

       if(ans==){

          printf("-1\n");

       }else

       printf("%d\n",ans);

    }

     return ;

 }

相关文章