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

题目

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

思路

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

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

二分即可
现在有个问题：

来自CXH
也就是共线情况
可以记录相同 $g(x,c)$g(x,c) 时 $x$x 的最小值即可
二分时候区间为 $(L,R]$(L,R] 保证 $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;
}