CF1845D Rating System 题解

题面

给定一个长度为 \(n\) 数列 \(a\)，保证每项都不为 \(0\)。初始时 \(x=0\)，然后对于 \(1\le i\le n\)，按顺序进行如下操作：

• 如果 \(x\ge k\)，则 \(x\rightarrow \max(k, x+a_i)\)，否则 \(x\rightarrow x+a_i\)。

你需要求出 \(k\)，使得 \(x\) 的值尽量大。

题解

如果我们不考虑 \(k\) 的影响，将 \(x\) 的变化曲线画出来，可以发现为一段折线。下面考虑 \(k\) 的影响：可以使一段趋势为向下的折线变化量为 \(0\)，那么 \(k\) 对总答案的贡献即为改变的这一段折线的变化量。考虑最大化该变化量，即在原数列中寻找最小区间和。

考虑处理出原数列的前缀和 \(sum\)，计算时枚举右端点 \(r\)，以 \(r\) 为右端点的区间最小区间和为 \(sum_r - \max\limits_{1 \le l < r} sum_l\)，开一个变量维护即可。总复杂度 \(\mathcal{O}(n)\)。

Code

//CodeForces - 1845D
#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::pair<valueType, valueType> ValuePair;

int main() {
    valueType T;

    std::cin >> T;

    for (int testcase = 0; testcase < T; ++testcase) {
        valueType N;

        std::cin >> N;

        ValueVector source(N);

        for (auto &iter: source)
            std::cin >> iter;

        std::partial_sum(source.begin(), source.end(), source.begin());

        ValuePair ans(0, 0);

        valueType maxSum = 0;

        for (auto const &iter: source) {
            ans = std::min(ans, std::make_pair(iter - maxSum, maxSum));

            maxSum = std::max(maxSum, iter);
        }

        std::cout << ans.second << '\n';
    }
}