题解 CF1373C 【Pluses and Minuses】

b6e0_ · 2020-06-27 14:56:56 · 题解

CF题面传送门 洛谷题面传送门 博客食用更佳

这段伪代码用C++来表示就是：

res=0;
for(init=0;;init++)
{
    cur=init;
    ok=true;
    for(i=0;i<s.size();i++)
    {
        res++;
        if(s[i]=='+')
            cur++;
        else
            cur--;
        if(cur<0)
        {
            ok=false;
            break;
        }
    }
    if(ok)
        break;
}
//最终要你输出这段程序中的res变量

要是模拟这段程序，时间复杂度为O(|s|^2)，肯定超时。理解程序意思，发现外循环每一次其实在找-的个数减去+的个数为-1,-2,-3\cdots的位置。很明显，这些位置是单调的，扫一遍就可以了，并不用像伪代码里一样一次又一次地循环找。

具体实现细节看代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
        string s;
        int i,sum=0,fi=-1,ans=0;//sum为+的个数减-的个数，fi为当前要找的差，ans为最终答案
        cin>>s;
        for(i=0;i<s.size();i++)
        {
            if(s[i]=='+')
                sum++;
            else
                sum--;
            if(sum==fi)//找到了
            {
                ans+=i+1;
                fi--;
            }
        }
        cout<<ans+s.size()<<endl;//伪代码中最后一次循环是从头扫到尾的，所以要额外加上|s|
    }
    return 0;
}

时间复杂度为O(|s|)。