题意

你有 N(1\leq N\leq 2\times 10^5) 本书，每本书都有一个编号 i(1\leq i\leq N) 和一个愉快度 A_i(-10^9\leq A_i\leq 10^9) 。现在有 K(1\leq K\leq N) 个同学，你要分给每个同学一段编号连续的书（至少一本）。一个同学的愉快度为他被分到的所有书的愉快度之和。你可以把最后的若干本书藏起来后将剩下的所有书分给这 K 名同学。求所有同学的愉快度的最大值的最小值。

思路

题目要求的是一个最大值的最小值，容易想到二分答案。check(mid) 表示愉快度的最大值是否可能小于等于 mid 。于是本题的主要任务就转化为实现 check 函数。

简单的贪心很容易举出反例，可以考虑 DP 。我们先求出 A 的前缀和数组 S 。定义一个序列 B 为 k-下降序列 ，它的每一个元素与前一个元素的差都不大于 k 。形式地说，对于每个 i(1\leq i<|B|) ，都有 B_{i+1}-B_i\leq k 。

回到题目，S_r-S_{l-1}(l\leq r) 可以表示区间 [l,r] 的书的愉快值之和，而所有选中区间的愉快值和都应小于等于 mid 。令 f(i) 表示由第 i 个元素开始，S 的最长mid-下降子序列的长度。与求最长下降子序列相似，容易得出状态转移方程 f(i)=\underset{i<j\leq N,S_j\leq S_i+k}{max}\;f(j)+1 。将 S 离散化，按 i 从大到小的顺序转移，用树状数组维护已经求出的 S_j 不大于 S_i+mid 的 f(j) 的最大值，即可 O(logn) 转移。由于 S_0 必须选，所以 f(0) 表示由 S_0 开始的 S 的最长mid-下降子序列的长度，f(0)-1 即为最多选出的区间数。若 f(0)-1\geq K ，则所有同学被分到的书都能满足要求，check(mid)=1 ；否则 check(mid)=0 。

代码

#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN=220000;
const int MAXV=1E9;
int n, m, c;
int a[MAXN], f[MAXN];
ll s[MAXN], sub[MAXN];
struct BIT
{
    int d[MAXN];
    inline int lb(int x) { return x&-x; }
    inline void init()
    {
        for (int i=1; i<=n; i++) d[i]=0;
    }
    inline void update(int x, int k)
    {
        if (x==0) return ;
        while (x<=n) d[x]=max(d[x], k), x+=lb(x);
    }
    inline int query(int x)
    {
        int res=0;
        while (x>0) res=max(res, d[x]), x-=lb(x);
        return res;
    }
} bit;
inline int read()
{
    int x=0, f=0; char ch=0;
    while (!isdigit(ch)) f|=ch=='-', ch=getchar();
    while (isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
    return f?-x:x;
}
inline void discretize()
{
    sort(sub+1, sub+n+1);
    c=unique(sub+1, sub+n+1)-sub-1;
}
inline int key(ll x)
{
    return upper_bound(sub+1, sub+c+1, x)-sub-1;
}
bool check(ll k)
{
    bit.init();
    for (int i=n; i>=0; i--)
    {
        f[i]=bit.query(key(s[i]+k))+1;
        bit.update(key(s[i]), f[i]);
    }
    return f[0]>m;
}
int main()
{
//  freopen("1004.in", "r", stdin);
//  freopen("1004.out", "w", stdout);
    int T=read();
    while (T--)
    {
        n=read(); m=read();
        for (int i=1; i<=n; i++) a[i]=read();
        for (int i=1; i<=n; i++) sub[i]=s[i]=s[i-1]+a[i];
        discretize();
        ll l=-1ll*n*MAXV, r=MAXV;
        while (l<r)
        {
            ll mid=(l+r)>>1;
            if (check(mid)) r=mid;
            else l=mid+1;
        }
        printf("%lld\n", l);
    }
    return 0;
}