识海社区打卡-3

Codeforces Round 986 (Div. 2)赛后补题

战况如下：

当然打完这场升绿了，虽然我也没想到。b题wa了很多发还是阅读理解的水平不太够，还没又补了一个样例说明我就看明白了不过还是wa了几发，不过确实用了我太长时间，欠训了。

比赛时c题我没有去实现，不过看样例猜了一个方法，赛后看答案我才发现我的想法是对的，艹了自己懒了没有争分夺秒去实现，不过半个小时以我半信半疑的态度确实想ac也有点困难，还是欠训了。jiangly群还有个大哥看最后一题看样例猜出来答案也是真离谱，欠训了，狠狠加训！

c题的题意大概是一个数组a分割成m +１份，所以切ｍ刀，和昨天的cf的c很像，昨天的c是数组中取出一个区间使得剩下最大，不过不同的是今天是动态规划，今天的是贪心。

解题思路大概就是先从前往后找能符合条件的切割点，再从后往前找能符合的切割点，然后两头切留下中间，再逐步找如此下去的最大值。不过这样子依旧有一个问题，就是如果符合条件的切割方法不足怎么办（所以我估计我自己就算当时实现这种方法也ac不了）。

还是老规矩看哥哥代码，看强者的代码才是变强最快的方法！

void solve() {
    int n, m, v;
    std::cin >> n >> m >> v;
    
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    
    std::vector<i64> pre(n + 1);
    for (int i = 0; i < n; i++) {
        pre[i + 1] = pre[i] + a[i];
    }
    
    i64 ans = -1;
    
    std::vector<int> f(m + 1), g(m + 1);
    for (int i = 1, j = 0; i <= m; i++) {
        while (j <= n && pre[j] - pre[f[i - 1]] < v) {
            j++;
        }
        f[i] = j;
    }
    g[0] = n;
    for (int i = 1, j = n; i <= m; i++) {
        while (j >= 0 && pre[g[i - 1]] - pre[j] < v) {
            j--;
        }
        g[i] = j;
    }
    
    for (int i = 0; i <= m; i++) {
        if (f[i] <= g[m - i]) {
            ans = std::max(ans, pre[g[m - i]] - pre[f[i]]);
        }
    }
    std::cout << ans << "\n";
}

好吧还是哥哥牛逼，因为如果不够切的话，切割点会少一个，这样对于每次查询来说pre[g[m - i]]都会在pre[f[i]]的左边，那么答案也就自然输出-1了。难怪昨天过b的人这么多过c。