Educational Codeforces Round 69 D Yet Another Subarray Problem 思维题
思维题   发布于 2019-07-23   517人围观  0条评论
思维题   发表于 2019-07-23   517人围观  0条评论

题目大意

求出给定序列的一个连续子序列,使得这个子序列的值的和sum与k*(子序列长度len)/m(除法做上取整)的差值最小。

题解

非常巧妙的一道思维题。

首先这个题用线段树维护最大子段和是错误的,我写线段树就一直WA on test 8.

听说还有写DP的,咱也不是很懂。

今天问的学长,学长说是把这些看成前缀和然后瞎搞就完事了。

然后……直到我看到榜单第3那个人写的东西的时候我才彻底搞清楚。

思路如下:

我们可以发现m很小,只有10,而当子段长度能整除以m的时候,再添加一个才会使得我们多去减一个k。

我们可以让所有位置对m取模,分成0——m-1这样的剩余系,我们枚举剩余系,以剩余系中的位置作为结尾求最大值。

当我们枚举到剩余系i的时候,我们另所有处于剩余系i的位置上的数-k,之后我们直接扫一遍序列,不断累加并和0求最大值,遇到可结束位置时,与答案取最大值并更新答案。

这样子我们可以再O(nm)的时间复杂度下做出这道题。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
int n,m,k;
int a[maxn],b[maxn];
typedef long long ll;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m >> k;
    for(int i = 1;i <= n;++i){
        cin >> a[i];
    }
    ll ans = 0;
    ll s = 0;
    for(int j = 0;j < m;++j){
        for(int i = 1;i <= n;++i)
            if(i % m == j)
                b[i] = a[i] - k;
            else b[i] = a[i];
        s = 0;
        for(int i = 1;i <= n;++i){
            s = max(s+b[i],0ll);
            if(i % m == j)ans = max(ans,s);    
        }
    }
    cout << ans << endl;
    return 0;
}


上一篇: 2019 Multi-University Training Contest 1 1004 Vacation

下一篇: Light OJ 1268 Unlucky Strings KMP DP矩阵快速幂优化

立即登录,发表评论
没有帐号?立即注册
0 条评论