2023牛客OI赛前集训营-提高组（第三场）C.分糖果

2023牛客OI赛前集训营-提高组（第三场）C.分糖果

C-分糖果_2023牛客OI赛前集训营-提高组（第三场） (nowcoder.com)

题目大意

求前 \(i(i\in[1, n])\) 个数分成 \(k\) 个连续的区间，每一个区间和的最大值最小是多少。

\(T\) 组数据

对于 \(30pts\) ，\(1 \le n \le 100 , 1\le k \le n\)

另外 \(20pts\) ，\(1\le n \le 10^4 , k = 1\)

另外 \(50pts\)，\(1\le n \le 10^5 , 1\le k \le n\)

对于全部数据有 \(T \le 3 , |a_i| \le 10^9 , 1\le n \le 10^5\)

做法

考试忘记加换行，\(50pts \to 0\)

对于 \(30pts\)

直接二分答案 + \(dp\) ， \(O(n^2)\) 判断能不能分成大于等于 \(k\) 块的和满足假设。

对于 \(20pts\)

直接前缀和乱搞

\(50pts\) 代码

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define LL long long
using namespace std;
const int N = 1e5 + 5 , M = 1e5 + 5;
const LL inf = 1e14 + 5;
int n , k;
LL a[M] , f[M] , s[M] , ans;
bool ck (LL x) {
    int l = 1;
    fu (i , 1 , n) f[i] = 0;
    fu (i , 1 , n) {
        if (i == 1) {
            f[i] = (s[1] <= x);
        }
        else {
            fu (j , 1 , i) {
                if (s[i] - s[j - 1] <= x && (f[j - 1] || j == 1)) f[i] = max (f[i] , f[j - 1] + 1);
            }
        }
        if (f[i] >= k) return 1;
    }
    return 0;
}
LL fans (LL l , LL r) {
    if (l == r) {
        return ck (l) ? l : inf;
    }
    LL mid = l + r >> 1;
    if (ck (mid)) return min (fans (l , mid) , mid);
    else return min (inf , fans (mid + 1 , r));
}
int main () {
    // freopen ("candy2.in" , "r" , stdin);
    int T; 
    scanf ("%d" , &T);
    while (T --) {
        scanf ("%d%d" , &n , &k);
        fu (i , 1 , n) scanf ("%lld" , &a[i]) , s[i] = 0;
        fu (i , 1 , n) s[i] = s[i - 1] + a[i];
        if (k == 1) {
            ans = inf;
            fu (i , 1 , n) ans = min (ans , s[i]);
            printf ("%lld\n" , ans);
            continue;
        }
        printf ("%lld\n" , fans (-inf , inf));
    }
}

对于 \(100pts\)

权值线段树 + 离散化

我们发现上面的 \(dp\) 转移太慢了

\(s\) 数组表示前缀和，当前二分答案为 \(x\)

对于 \(i\in[1 , n]\) 我们只用找到 \(j\in[1 , i]\) 满足 \(s[i] - s[j] \le x\) 即 \(s[i] - x \le s[j]\) 时的最大值 \(+1\)

即

\[f[i] = MAX_{j = 1}^i f[j] + 1(s[i] - x \le s[j]) \]

用权值线段树维护就好了。

初始化 \(f[0] = 0\)

每次把 \(f[i]\) 插入权值线段树中

因为总和太大了，所以还要把 \(s[i]\) 和 \(s[i] - x\) 拿出来离散化（还有 \(0\)），动态开点。

#include <bits/stdc++.h>
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define LL long long
using namespace std;
const int N = 4e7 + 5 , M = 2e5 + 5;
const LL inf = 1e9 * 1e6;
const int inff = 1e9 + 5;
int n , k , cnt , mp[M];
LL a[M] , f[M] , s[M] , ans , ss[M << 1];
struct Tr {
    int v , lp , rp;
} tr[N];
void glp (int p) {
    if (!tr[p].lp) {
        tr[p].lp = ++cnt;
        tr[cnt].v = -inff;
    }
}
void grp (int p) {
    if (!tr[p].rp) {
        tr[p].rp = ++cnt;
        tr[cnt].v = -inff;
    }
}
void change (int p , LL l , LL r , int x , int val) {
    if (l == r) tr[p].v = max (tr[p].v , val);
    else {
        int mid = l + r >> 1;
        if (x <= mid) {
            glp (p);
            change (tr[p].lp , l , mid , x , val);
        }
        else {
            grp (p);
            change (tr[p].rp , mid + 1 , r , x , val);
        }
        tr[p].v = max (tr[tr[p].lp].v , tr[tr[p].rp].v);
    }
}
int query (int p , LL l , LL r , LL L , LL R) {
    if (L <= l && R >= r) return tr[p].v;
    else {
        int mid = l + r >> 1 , ans1 = -inff , ans2 = -inff;
        if (L <= mid && tr[p].lp) 
            ans1 = query (tr[p].lp , l , mid , L , R);
        if (R > mid && tr[p].rp) 
            ans2 = query (tr[p].rp , mid + 1 , r , L , R);
        return max (ans1 , ans2);
    }
}
void cl (int p) { tr[p].lp = tr[p].rp = 0 , tr[p].v = -inff; }
void clear (int p , LL l , LL r) {
    if (l == r) {
        cl (p);
        return;
    }
    int mid = l + r >> 1;
    if (tr[p].lp) 
        clear (tr[p].lp , l , mid);
    if (tr[p].rp)
        clear (tr[p].rp , mid + 1 , r);
    cl (p);
} 
bool ck (LL x) {
    int s1 = 1;
    ss[1] = 0;
    fu (i , 1 , n) {
        ss[++s1] = s[i];
        ss[++s1] = s[i] - x;
    }
    sort (ss + 1 , ss + s1 + 1);
    int m = unique (ss + 1 , ss + s1 + 1) - ss - 1;
    clear (1 , -M , M);
    tr[0].v = -M;
    cnt = 1;
    int y = lower_bound(ss + 1 , ss + s1 + 1 , 0) - ss;
    change (1 , -M , M , y , 0);
    fu (i , 1 , n) {
        y = lower_bound(ss + 1 , ss + s1 + 1 , s[i] - x) - ss;
        f[i] = query (1 , -M , M , y , M) + 1;
        y = lower_bound(ss + 1 , ss + s1 + 1 , s[i]) - ss;
        change (1 , -M , M , y , f[i]);
        if (f[i] >= k) return 1;
    }
    return 0;
}
LL fans (LL l , LL r) {
    if (l == r) return ck (l) ? l : inf;
    else {
        LL mid = l + r >> 1;
        if (ck (mid))  {
            return min (fans (l , mid) , mid);
        }
        else {
            return fans (mid + 1 , r);
        }
    }
}
int main () {
    // freopen ("candy2.in" , "r" , stdin);
    int T; 
    scanf ("%d" , &T);
    while (T --) {
        scanf ("%d%d" , &n , &k);
        fu (i , 1 , n) scanf ("%lld" , &a[i]) , s[i] = 0;
        fu (i , 1 , n) s[i] = s[i - 1] + a[i];
        printf ("%lld\n" , fans (-inf , inf));
    }
}