Codeforces Round #410 (Div. 2)-B. Mike and strings【STL+略贪心】

题意:已知n个字符串,问经过多少次操作可以使得所有字符串相等。 每次操作: 对于当前字符串,把s[0]放到s的最后一个

思路:首先明确一点,次数最少,我们必须得以某一个字符串s为原型,其他去尽可能靠近s(合理)。以每一个字符串s为基础,对于其他字符串,因为头会到尾部,那么我们把字符串t*2(首尾相连)。 用string find函数在字符串*2中去寻找s,如果没找到那么会返回string::npos。 如果找到了,会返回该字符串的前一个下标。比如s=’a’ t=’baa’ 那么t.find(s)=1 正好就是把前面放到后面的次数。

数据分析:1 ≤ n ≤ 50

复杂度分析:O(n^2)

学习了:string s1,s2; s1.find(s2) 在中寻找s2,如果找到了返回前一个下标,否则返回string :: npos。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

string s[60];

int main(void)
{
    int n;
    cin >>n ;
    for(int i=1;i<=n;i++)
        cin >> s[i];
    int ans=INT_MAX;
    for(int i=1;i<=n;i++)
    {
        int cnt=0;
        for(int j=1;j<=n;j++)
        {
            string temp=s[j]+s[j];
            if(temp.find(s[i])==string::npos)
            {
                printf("-1\n");
                return 0;
            }
            else
                cnt+=temp.find(s[i]);
        }
        ans=min(ans,cnt);
    }
    cout << ans <<endl;
}
全部评论

相关推荐

昨天 13:43
门头沟学院 Java
longerluck...:我猜说的是“你真**是个天才”
投递美团等公司10个岗位
点赞 评论 收藏
分享
门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务