><

直接寫中文了

Problem Statement

給定的是長度為N-1的字串S. S中的每個字符都是<或>，

當對所有i（1≤i≤N-1）都滿足以下條件時，N個非負整數a1，a2，[cdots]，aN的序列被認為是滿足的

如果Si = <：ai <ai + 1
如果Si =>：ai> ai + 1

找出N個非負整數的良好序列的元素的最小可能和，

約束條件

2≤N≤5×10⁵
S是長度為N-1的字串，由<和>組成

Input

輸入來自標準輸入，格式如下：

Output

找出N個非負整數的良好序列的元素的最小可能和，

Sample Input 1

<>>

Sample Output 1

a =（0,2,1,0）是一個好序列，其總和為3，沒有一個好序列，其總和小于3

Sample Input 2

<>>><<><<<<<>>><

Sample Output 2

題目鏈接：
https://vjudge.net/problem/AtCoder-5659

不難發現找到"<>"這個即可

"<>"左右兩邊的個數設為l，r；大的一個為maxn，小的一個為minn ，則兩邊的和為（maxn+1）/2*maxn+（minn+1）/2*minn-minn

"><"左右兩邊的個數設為l，r；兩邊的和為（l+1）/2*l+（r+1）/2*r

所以只要遍歷一遍s即可，碰到"<>"另外討論，其他情況假設有n個"<"或者">"，則ans+=(n+1)/2*n;

AC代碼

#include <bits/stdc++.h>
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x, y) memset(x, y, sizeof(x))
#define Maxn 1000000000000 + 10
using namespace std;
string s;
ll len;
ll ans;
void solve(ll start, ll sum, ll flag) //搜索起始位置，上一次共有sum個連續的<或者>,上一次有沒有出現<>
{
    ll i;
    ll f = 0;
    ll cnt = 1; //計數
    char r = s[start];
    for (i = start + 1; i < len; i++)
    {
        if (s[i] == r)
            cnt++;
        else
        {
            if (r == '<' && s[i] == '>') //存在<>,f=1
                f = 1;
            break;
        }
    }
    if (flag == 1)
    {
        if (cnt > sum)
        {
            if (cnt > 1)
            {
                ans += (cnt + 1) * cnt / 2;
                ans -= sum;
            }
            else
            {
                ans += 1;
                ans -= sum;
            }
        }
        else
        {
            if (cnt > 1)
            {
                ans += (cnt + 1) * cnt / 2;
                ans -= cnt;
            }
            else
            {
                ans += 1;
                ans -= cnt;
            }
        }
        if (i >= len)//遍歷完成
            return;
        return solve(i, cnt, f);
    }
    else
    {
        if (cnt > 1)
            ans += (cnt + 1) * cnt / 2;
        else
        {
            ans += 1;
        }
        if (i >= len)//遍歷完成
            return;
        return solve(i, cnt, f);
    }
}
int main()
{
    ans = 0;
    cin >> s;
    len = s.size();
    solve(0, 0, 0);
    cout << ans << endl;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/128446.html

標籤：其他

上一篇：資料結構篇——并查集

下一篇：矩形覆寫

【AtCoder - 5659 】>< （思維題）

><