You are given a string s of length n , where each character is either < or >. An array a consisting of n+1 elements is compatible with the string s if, for every i from 1 to n , the character si represents the result of comparing ai and ai+1 , i. e.: si is < if and only if ai<ai+1 ; si is > if and only if ai>ai+1 . For example, the array [1,2,5,4,2] is compatible with the string <<>>. There are other arrays with are compatible with that string, for example, [13,37,42,37,13] . The cost of the array is the number of different elements in it. For example, the cost of [1,2,5,4,2] is 4 ; the cost of [13,37,42,37,13] is 3 . You have to calculate the minimum cost among all arrays which are compatible with the given string s .c++代码
时间: 2024-01-16 12:02:28 浏览: 69
这是一道非常经典的贪心算法题目,可以通过扫描字符串 s 来构造符合条件的数组。具体来说,我们从左到右扫描 s,同时维护当前的最小值和最大值,以及当前的数组元素个数。每当遇到一个字符 <,就将当前的最大值插入数组,然后将最大值加一;每当遇到一个字符 >,就将当前的最小值插入数组,然后将最小值减一。注意,如果当前的最小值和最大值相等,需要将它们分别插入数组,并将最大值加一、最小值减一。最后,数组的大小就是最小的代价。
以下是详细的 C++ 实现:
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
string s;
cin >> s;
int n = s.size();
int mn = 0, mx = 0, ans = 1;
vector<int> a(n+1);
a[0] = 0;
for (int i = 0; i < n; i++) {
if (s[i] == '<') {
a[i+1] = ++mx;
} else {
a[i+1] = --mn;
}
ans += (a[i+1] == a[i]);
}
cout << ans << endl;
return 0;
}
```
时间复杂度为 O(n),其中 n 是字符串 s 的长度。