codeforces 2089B1 题解

前言

对我来说很难的一道题。看20分钟后没有思路去看了题解但是没看明白，自己想到了二分的假做法（最后发现是错的），找到错误后开始理解题解思路，最后AC掉的一道题。

---

题意

有两个数组a和b，每次对a和b进行连续的2个操作：

• 对每个合法的$i$，将 $a[i]$ 和 $b[i]$ 减少$min(a[i], b[i])$
• 将$a$逆时针移动 $a[i] = a[(i + n - 1) \ \%\ n]$

求多少次操作后a中所有元素都变为0。

思路

假设第k次操作后a中所有元素变为0，那么对于1~n的每一个i，$\Sigma_{j = i}^{i + k - 1}(a[i]-b[i]) \leq 0$。

考虑使用前缀和预处理和式，那么我们要做的就是对每一个i，找到最小的k使得不等式成立；

至此，题意可以转化为对每一个i，找到最小的k，使得$sum[i + k - 1] <= sum[i]$,显然此时上面提到的不等式成立。

由于n的范围为2e5，暴力求解复杂度为$O(n^2)$不可接受。

为了解决这个新的问题，codeforces官方题解提出了一个“括号匹配”的例子，但其实这个例子我看的迷迷糊糊的。

我们想找到sum数组中每个元素后出现的第一个比这个元素小的元素，可以考虑使用单调队列q维护每个元素的值和索引，用int数组to[idx]维护第idx个元素后出现的第一个比sum[idx]小的元素，并进行如下操作：

1. 对于一个新的元素x，如果q为空，将其压入q；
2. 若q非空，将q栈顶元素与x比较，若x<=q.top().val，更新to[q.top().idx] = i

最后遍历1~n，找到最大的to[i] - i即可。

注意题目为一个环，需要将环拆成两倍大小的一维数组。

#include <bits/stdc++.h>
#define int long long	// 一开始忘开long long了
using namespace std;

const int N = 4e5 + 7;
int n, k;
int a[N], b[N];
int sum[N];
int to[N];

void solve() {
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i) cin >> b[i];

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

    for(int i = 1; i <= 2 * n; ++i) {
        sum[i] = sum[i - 1] + a[i] - b[i];
    }
    
    int ans = 0;
    priority_queue<pair<int, int>> q;
    for(int i = 1; i <= 2 * n; ++i) {
        while(q.size() and -q.top().first >= sum[i]) {
            to[q.top().second] = i;
            q.pop();
        }
        q.push({-sum[i], i});	// 存入-sum[i], 将大根堆变作小根堆使用，取值时加负号即可 
    }

    for(int i = 1; i <= n; ++i) {
        ans = max(ans, to[i] - i);
    }
    
    cout << ans << endl;
}

signed main() {
    int t;  cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

后记

说实话这道题对我来说还是太难了，我赛时估计够呛想得出思路。其实这道题关键还是在于将问题转化为和式不等式成立问题，求到这一步后，写完题解我才意识到有很多方法可以过掉（比如对k二分答案，时间复杂度和单调队列一样，但是正确性我没有验证过）。