【2018南京】 Tournament (dp + 决策单调性 + wqs 二分)

There are $a_iaikilometers to the east of the village chief's house. (For simplicity, the 00-th villager is the village chief, so a_0=0a0=0.)$

Recently, a tournament is going to be held in Number Village, in which everyone in the village will participate.

For the convenience of villagers, the organizer plans to build

However, the organizer wants the traffic cost to be minimized. The traffic cost is defined by $sum_{i=0}^{N-1} min_{j=0}^{K-1} D(a_i, s_j)∑i=0N−1minj=0K−1D(ai,sj), where D(a_i, s_j)D(ai,sj) is the distance between the ii-th villager's house and the jj-th stadium.$

Your task is to calculate the minimal traffic cost (rounded down to the nearest integer), given $a_iai.$

Input

The first line contains two positive integers $10^ 5K≤N≤3×105).$

The second line contains $a_0,a_1,cdots,a_{N-1}a0,a1,⋯,aN−1 (0=a_0<a_1<cdots<a_{N-1}leq 10^ 90=a0<a1<⋯<aN−1≤109).$

Output

Print a single integer

样例输入1

5 2
0 4 7 9 10

样例输出1

样例输入2

9 3
0 1 10 11 20 21 22 30 32

样例输出2

题目来源

ACM-ICPC Nanjing Onsite 2018

SOLUTION:

我这份题解并没有a，可能是二分的地方常数太大导致T了，但是可以当作模板

wqs二分之后，变成了O^2的dp，然后使用单调队列来进行优化

一类导数递增求最小值，或者导数递减求最大值，需要使用单调队列

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
#define N 300010

ll n,k,s[N],f[N],w[N],ans=0;
int q[N];

ll a[N]; int isx[N];
inline ll calc(int &j,int &i)
{
    int mid=i+j+1>>1;
    ll now=s[mid]-s[mid-1];
  //  return f[j]+s[i]+s[j]-2*s[mid]+((i-j)&1?now:0);
    mid=i+j+1>>1;
    return f[j]+(s[i]-s[mid]-(i-mid)*a[mid])+((mid-j-1)*a[mid]-(s[mid-1]-s[j]));

}
inline bool better(int &k1,int &k2,int &i)
{
    ll val1=calc(k1,i),val2=calc(k2,i);
    if(val2<val1)
        return 1;
    if(val1<val2)
        return 0;
    return w[k2]<=w[k1];
}

inline int bound(int &a,int &b,int o)
{
    int l=b+1,r=o?o:n+1,ans=r+1;
    while(l<=r)
    {
        int mid=l+r>>1;
       // if(calc(a,mid)>=calc(b,mid))ans=mid,r=mid-1;
        if(better(a,b,mid))ans=mid,r=mid-1;
        else l=mid+1;
    } return ans;
}

inline int  jud(ll mid)
{
    int qh=1,qt=0;
    q[++qt]=0;
    for(int i=1;i<=n;++i)
    {
        while(qh<qt&&isx[qh]<=i)++qh;
        f[i]=calc(q[qh],i)+mid;
        w[i]=w[q[qh]]+1;
        while(qh<qt&&isx[qt-1]>=bound(q[qt],i,isx[qt-1]+1))
            --qt;
        isx[qt]=bound(q[qt],i,0);
        q[++qt]=i;
    }
    return w[n];
}inline int read()
{
	int X=0; bool flag=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') flag=0; ch=getchar();}
	while(ch>='0'&&ch<='9') {X=(X<<1)+(X<<3)+ch-'0'; ch=getchar();}
	if(flag) return X;
	return ~(X-1);
}

signed main()
{
    n=read(); k=read();
        ans=0;
        for(int i=1;i<=n;i++)isx[i]=0;
        for(ll i=1;i<=n;i++)
        {
            s[i]=read();
            a[i]=s[i];
            s[i]+=s[i-1];
        }
        ll l=0,r=s[n];
        while(l<=r)
        {
            ll mid=l+r>>1;
            if(jud(mid)<=k)
            {
                r=mid-1;
                ans=f[n]-k*mid;
            }
            else
                l=mid+1;
        }
        printf("%lld
",ans);

    return 0;
}