差分数组和贪心

算法

错字

平衡括号字符串：最简单的定义为字符串所包含的 ( 和 ) 数量必须相同，并且对于字符串的任意前缀，所包含的 ( 的数目都不少于 ) 的数目。（准确来说是左括号严格等于右括号）

题目意思理解准确：①任意前缀。②可能是(多于),也有可能是)多于(,(等于)时，一定是满足平衡括号字符串。

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

string s;

int main() {
    cin >> s;
    
    int l = 0, r = 0;
    for(auto c : s) {
        if(c == '(')    l ++;
        else    r ++;
    }
    
    if(l == r)  puts("0");
    else if(l < r) {
        int a = 0, b = 0;
        for(auto c : s) {
            if(c == '(')    a ++;
            else {
                b ++;
                if(b > a) {
                    cout << b << endl;
                    break;
                }
            }
        }
    }
    else {
        int a = 0, b = 0;
        reverse(s.begin(), s.end());
        for(auto c : s) {
            if(c == ')')    a ++;
            else {
                b ++;
                if(b > a) {
                    cout << b << endl;
                    break;
                }
            }
        }
    }
    
    return 0;
}

`distance()`函数

distance() 函数用于计算两个迭代器表示的范围内包含元素的个数，其语法格式如下：

template
typename iterator_traits::difference_type distance (InputIterator first, InputIterator last);

其中，first 和 last 都为迭代器，其类型可以是输入迭代器、前向迭代器、双向迭代器以及随机访问迭代器；该函数会返回[first, last)范围内包含的元素的个数。例：

vector<int> data = { 1, 2, 4, 5, 5, 6 };
auto iter = lower_bound(data.begin(), data.end(), 2);
cout << distance(data.begin(), iter);
// 表示大于等于2的第一个元素的索引位置

Helping the Nature

首先维护一个差分数组，目的是用来得到相邻的下标的值，然后让所有值变得一样，选取第一个元素，如果其他元素比第一个小，那就让第一个元素减小到这个元素，否则其他元素比第一个元素的值大，就让其他后面元素减小到第一个元素的值，最后再让所有元素增加1即可。

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N = 200010;

LL a[N], b[N];

int main() {
    int T;
    cin >> T;
    while(T --) {
        int n;
        cin >> n;
        for(int i = 0; i < n; i ++)
            scanf("%lld", &a[i]);

        for(int i = 1; i < n; i ++)
            b[i] = a[i] - a[i - 1];

        LL res = 0;
        for(int i = 1; i < n; i ++) {
            if(a[i] < a[0]) {
                res += a[0] - a[i];
                a[0] = a[i];
            }
            else {
                res += a[i] - a[0];
                a[i] = a[0];
            }
            
            a[i + 1] = a[i] + b[i + 1];
        }
        res += abs(a[n - 1]);

        cout << res << endl;
    }

    return 0;
}