2019杭电多校第三场 HDU 6606

题意

一个n个数字的序列，要分给k个人，使每个人和的最大值最小，注意可以舍弃最后的任意多个数字

题解

二分答案
考虑二分最小值为 $K$K
$dp\left[i\right]$dp[i] 表示前 $i$i 个数最多能分成几段，则
$dp\left[i\right]=max\left\{dp\right[j]+1\mid sum[i]-sum[j]⩽k\}$dp [i]=max{ dp[j]+1 ∣  sum[i]−sum[j]⩽k}
直接 $dp$dp ,时间复杂度为 $n^2$n2 ,会 $TLE$TLE
考虑用权值线段树，将所有的前缀和离散化，每次查询满足 $sum\left[i\right]-K$sum[i]−K 的 $dp$dp 最大值
然后将自己的值插入到对应的位置

代码

#include<bits/stdc++.h>
#define N 200010
#define INF 0x3f3f3f3f
#define eps 1e-10
// #define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x) memset(x,0,sizeof x)
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std;
typedef pair<int,int> pi;
int n,m,cnt;
int a[N],dx[N];
LL c[N],s[N];

struct SegTree
{
    LL a[N<<2];int b[N<<2];
    int query(int x,int l,int r,LL s) {
        if (l==r) if (a[x]>=s)return b[x];else return -INF;
        if (a[x]>=s) return b[x];
        int t=l+r>>1;
        if (a[x<<1|1]<=s) query(x<<1|1,t+1,r,s);else
        return max(query(x<<1,l,t,s),query(x<<1|1,t+1,r,s));
    }
    void updata(int x,int l,int r,int pos,int y){
        if (l==r){b[x]=max(b[x],y); return;}
        int t=(l+r)>>1;
        if (pos<=t) updata(x<<1,l,t,pos,y);else
            updata(x<<1|1,t+1,r,pos,y);
        b[x]=max(b[x<<1],b[x<<1|1]);  
    }
    void build(int x,int l,int r){
        if (l==r) {a[x]=c[l],b[x]=-INF;return;}
        int t=(l+r)>>1;
        build (x<<1,l,t);
        build (x<<1|1,t+1,r);
        a[x]=min(a[x<<1],a[x<<1|1]);  
        b[x]=-INF; 
    }
}ST;
int dp[N];

bool check(LL x){
    ST.build(1,1,cnt);
    ST.updata(1,1,cnt,dx[0],0);
    int mx=-INF;
    for(int i=1;i<=n;i++){
        int t=ST.query(1,1,cnt,s[i]-x);
        dp[i]=t+1; 
        if(dp[i]>=m) return 1;
        ST.updata(1,1,cnt,dx[i],dp[i]);
    }
    return 0;
}

int main()
{
    int T;
    sc(T);
    while(T--){
        scc(n,m);
        for(int i=1;i<=n;i++) sc(a[i]),s[i]=s[i-1]+a[i],c[i]=s[i];
        c[n+1]=0;sort(c+1,c+n+2);
        cnt=unique(c+1,c+n+2)-c-1;
        for(int i=0;i<=n;i++) dx[i]=lb(c+1,c+cnt+1,s[i])-c;
        LL l=-1e15,r=1e9,ans;
        while(l<=r){
            LL t=l+r>>1;
            if (check(t)) ans=t,r=t-1;else l=t+1;
        }
        printf("%lld\n",ans);
    }
    return 0;
}