Distribution of books(线段树优化DP)

题目链接

https://cn.vjudge.net/problem/HDU-6606

题目大意

n个数,连续的一段分为一份,总共分为k份,要求每份和的最大值尽量小。
1<=n<=2e5,-1e9<=ai<=1e9,1<=k<=n
note:不一定分完

解题思路

标称里那诡异的离散化真给我看跪了emmm

题目要使得最大值最小?考虑二分答案
对于每次二分答案(假设为x),如何判定x能否满足分为k份的要求呢?考虑动态规划
dp[i]表示前i个数最多能分成几段, 则
if(sum[i] - sum[j] <= x)
dp[i] = max(dp[j]) + 1;
但是这样转移肯定等会超时,所以用线段树维护max(dp[j])在sum[i]-x到sum[i]之间

代码

#include <bits/stdc++.h>
using namespace std;
const long long maxn=2e5+100;
const long long inf=1e18;
long long a[maxn],b[maxn];
long long n,k,tot;
struct node{
    long long l,r,data;
}tr[maxn*4];
void build(long long o,long long l,long long r){
    tr[o].data=0;
    tr[o].l=l;
    tr[o].r=r;
    if(l==r)return;
    long long mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
}
long long query(long long o,long long l,long long r){
    if(l<=tr[o].l&&r>=tr[o].r)return tr[o].data;
    long long ret=0;
    long long mid=(tr[o].l+tr[o].r)>>1;
    if(l<=mid)ret=max(ret,query(o<<1,l,r));
    if(r>mid)ret=max(ret,query(o<<1|1,l,r));
    return ret;
}
void update(long long o,long long pos,long long val){
    if(tr[o].l==tr[o].r){
        tr[o].data=max(tr[o].data,val);
        return;
    }
    long long mid=(tr[o].l+tr[o].r)>>1;
    if(pos<=mid)update(o<<1,pos,val);
    if(pos>mid)update(o<<1|1,pos,val);
    tr[o].data=max(tr[o<<1].data,tr[o<<1|1].data);
}
bool check(long long mid){
    build(1,1,tot);
    long long sum=0,mxsum=0;
    for(long long i=1;i<=n;i++){
        sum+=a[i];
        if(sum-mid>mxsum)continue;
        long long pos=lower_bound(b+1,b+1+tot,sum-mid)-b;
        long long dp=query(1,pos,tot)+1;

        pos=lower_bound(b+1,b+1+tot,sum)-b;
        update(1,pos,dp);
        mxsum=max(mxsum,sum);
        if(dp==k)return true;
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        cin>>n>>k;
        b[0]=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            b[i]=b[i-1]+a[i];
        }
        sort(b+1,b+1+n);
        b[0]=-1e9+7;
        tot=0;
        for(int i=1;i<=n;i++){
            if(b[i]!=b[i-1])
                b[++tot]=b[i];
        }
        long long l=-inf,r=inf,ans;
        check(-1);
        while(l<=r){
            long long mid=(l+r)>>1;
            if(check(mid)){
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        cout<<ans<<endl;
    }
    return 0;
}

1 thought on “Distribution of books(线段树优化DP)”

发表评论

电子邮件地址不会被公开。 必填项已用*标注