Codeforces 1358E - Are You Fired? 题解

好几天没更新了

题解 #

首先，先定义这个函数 $f_k(i)=a_i+a_{i+1}+\dots +a_{i+k-1}$ ，也就是从 $i$ 开始往后连续 $k$ 个数的和。

然后我们证明如果 k 和一个答案那么 2k 也是一个答案： $f_{2k}(i)=f_k(i)+f_k(i+k)>0$ 。因此我们从能找到一个大于 $\dfrac n 2$ 的答案。

然后我们分类讨论，先考虑 $x\ge 0$ 的情况。如果 k 是答案，因为 $f_{k+1}(i)=f_k(i)+a_{i+1}=f_k(i)+x>0$ ，所以 k+1 也是一个答案，因此我们只要判断 $k=n$ 是不是答案就行了。

最后，考虑 $x\leq 0$ ，我们需要借助以下前缀和，定义 $pre_i=a_0+a_1+\dots+a_{i-1},i>0$ 并且 $pre_0=0$ . 我们需要找到 $k$ 使得对于所有 $0\leq i\leq n-k$ :

\begin{aligned}pre_{i+k}-pre_i&>0 \\\ pre_{i}&< pre_{i+k}\end{aligned}

因为 $k>\dfrac n 2$ ，“窗口”之后的所有数字都是 $x$ ，所以上面的不等式可以写成这样：

\begin{align*}pre _i& < pre _n-x\cdot(n-k-i) \\\ pre_i+x\cdot(n-i)&< pre _n+x\cdot k\end{align*}

对于每一个 $i$ ，对应的 k 是 $n-1$ ，也就是说不等式左边的最大值如果小于 $pre_n+x\cdot (n-i)$ ，那么 $k=n-i$ 是一个答案。

Code #

#include <bits/stdc++.h>
 
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define all(x) (x).begin(), (x).end()
 
using namespace std;
using ll = long long;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> a(n);
    forn(i, (n + 1) / 2) {
        cin >> a[i];
    }
    int x;
    cin >> x;
    for (int i = (n + 1) / 2; i < n; i++) a[i] = x;
    vector<ll> ps(n + 1);
    partial_sum(all(a), ps.begin() + 1);
    if (ps.back() > 0) return cout << n, 0;
    if (x >= 0) return cout << -1, 0;
    ll N2 = n / 2, N1 = n - N2, sum = ps.back();
    ll mx = -1e18;
    for (int i = 0; i <= N1; i++) {
        mx = max(mx, ps[i] + x * ll(n - i));
        if (mx < sum + x * ll(n - i)) {
            cout << n - i;
            return 0;
        }
    }
    cout << -1;
    return 0;
}