题解 AT5659 【[AGC040A] ><】
rui_er
2020-02-12 10:53:38
~~看一下这道题的题面，决定放弃这道题，~~突然想起在 $\text{Atcoder}$ 上可能会有英文翻译，便到原题看了一眼，真的有。题意大概是：
- 输入一个仅由 $\lt$ 和 $\gt$ 组成的字符串 $s$ ，假设共 $l$ 位；
- 请你构造一个共 $l+1$ 位数列 $a$ ，满足 $\sum a_i$ 最小，同时 $a_i$ 与 $a_{i+1}$ 的关系是 $s_i$ 中的字符（即：大于或小于）。
- 输出 $\sum a_i$
看了一眼数据规模，想到一个 $O(n)$ 的暴力解法：
- 从前往后扫一遍字符串，构造 $s_i='\lt'$ 对应的值，具体方法： $a_{i+1}=a_i+1$ ，可以证明这是最优方案；
- 从后往前扫一遍字符串，构造 $s_i='\gt'$ 对应的值，具体方法： $a_i=\max(a_i, a_{i+1}+1)$ ，可以证明这是最优方案。
最后再扫一遍记好的数组，记录 $ans=\sum a_i$ ，输出即可，**注意 $ans$ 可能需要使用 $\text{long long}$**。
代码：
```cpp
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
string s;
ll l, a[500001];
ll ans;
int main()
{
cin>>s;
s = " " + s;
l = s.length() - 1;
for(int i=1;i<=l;i++) (s[i] == '<') ? (a[i+1] = a[i] + 1) : (a[i+1]);
for(int i=l;i>=1;i--) (s[i] == '>') ? (a[i] = max(a[i], a[i+1]+1)) : (a[i]);
for(int i=1;i<=l+1;i++) ans += a[i];
cout<<ans<<endl;
return 0;
}
```