本题思路
本题想要求得和的最小值那么便要求每个值尽可能的小而这个数又是非负数那么便先设想每个值都为零
先从左到右处理 < 号倘若碰上连续的 < 那么就让对应的值增加 否则就先不动
再从右到左处理 > 号碰上连续的就让其对应的值增加
因为要同时满足两边的性质 那么就要取二者每个对应位置上的的max
最后再遍历一遍加和即可
题目描述
(中文翻译版本)
人们的目光总是聚焦于身边的人。
序列也是这样。现在,你有一个长度为n的序列a,序列中的每个元素非负。定义序列S表示序列a中相邻两个数的大小关系:
Si=’<’, 表示ai < ai+1
Si=’>’, 表示ai > ai+1
现在,给定序列S,求出序列a中元素和的最小值。
(2 ≤ N ≤ 5*105)
S是一个由’<’和’>’组成的长度为N-1的序列
Input
一行一个序列S
Output
一行一个整数,表示序列a中元素之和的最小值。
样例
Sample Input 1
<>>
Sample Output 1
3
(a=(0,2,1,0))是一个满足约束条件S的序列 ,且元素之和为3。显然,没有其他满足条件的序列a使得元素和<3。
Sample Input 2
<>>><<><<<<<>>><
Sample Output 2
28
C++ 代码
#include<iostream>
using namespace std;
const int N=5e5+10;
string s;
int a[N];
int main()
{
cin>>s;
int n=s.length()+1;//n个比较关系符号有n+1个数
long long sum=0;
//从左到右遍历<
for(int i=0,cnt=0;i<n;i++)
{
a[i]=max(a[i],cnt);
if(i<s.length()&&s[i]=='<') cnt++;
else cnt=0;
}
//从右到左遍历>
for(int i=s.length(),cnt=0;i>=-1;i--)
{
a[i+1]=max(a[i+1],cnt);
if(i>=0 &&s[i]=='>') cnt++;
else cnt=0;
}
for(int i=0;i<n;i++)
sum+=a[i];
cout<<sum<<endl;
return 0;
}