数据备份[APIO/CTSC 2007][WQS二分]

题目

Luogu
$n$ 个点在 $x$ 轴上，位置 $p_i$，求配对 $k$ 对距离之和最小值
$n，k\le 10^5$

思路

主要是复习 $WQS$ 二分原理
记 $f(x)$ 为配对 $x$ 的最小值
显然答案递增，理解为凸函数

然后记每次划分会有附加权值 $c$
记 $g(x,c)$ 为有划分权值前提下划分 $x$ 个的最小值
那么有 $g(x,c)=f(x)+cx$
因为后面的 $cx$ 并不会影响决策
（凸函数叠加一次函数还是凸函数,和决策无关）
移项可得：
$$f(x)=?cx+g(x,c)$$
画图可得：

二分即可
现在有个问题：

来自CXH
也就是共线情况
可以记录相同 $g(x,c)$ 时 $x$ 的最小值即可
二分时候区间为 $(L,R]$ 保证 $R$ 始终合法即可

代码

#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstdio>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define LL long long
#define ULL unsigned long long
using namespace std;
LL read(){
    LL f=1,x=0;char c=getchar();while(c<'0'||'9'<c){
    if(c=='-')f=-1;c=getchar();}while('0'<=c&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return f*x;
}
#define MAXN 500000
#define INF 0x3f3f3f3f
int n,k;
LL p[MAXN+5],f[MAXN+5],g[MAXN+5];
int check(LL c){
    //f[i]:前i个最小值,g:f前提下最小划分段数memset(f,0x3f,sizeof(f));f[0]=0,f[1]=0;for(int i=2;i<=n;i++){
    f[i]=f[i-1],g[i]=g[i-1];if(f[i]>f[i-2]+p[i]-p[i-1]+c)f[i]=f[i-2]+p[i]-p[i-1]+c,g[i]=g[i-2]+1;else if(f[i]==f[i-2]+p[i]-p[i-1]+c)g[i]=min(g[i],g[i-2]+1);}return g[n];
}
int main(){
    n=read(),k=read();for(int i=1;i<=n;i++)p[i]=read();LL L=-p[n]-1,R=0;while(L+1<R){
    LL Mid=(L+R)>>1;if(check(Mid)<=k)R=Mid;else L=Mid;}check(R);printf("%lld\n",f[n]-k*R);return 0;
}