前面的话

这篇博客大概是带权二分(wqs 二分，是叫这个名字吧)的入门博客，希望大家点个赞👍。

引入

给你一个序列 。其中 。可以把序列分为 段。定义每一段的价值为 ，现在要求 的总和最小。形式的，我们要最小化 。

分析

• 我们可以先做一个 的线性 。定义 为 结尾，分了 的最小值。那么转移为 。最后的答案为 。我们再考虑一下优化。

• 我们可以分析，由于 。所以我们其实要分的段数要越多越好。那么我们得到第一个性质 ，答案是关于段数 的增加而减小的，而且减小值越来越小，因为 ，而我们一定是优先选择 操作的 。所以如果我们定义 。那么 是一个单调下降的，而且是一个上凸函数。那么我们可以借助图像分析一下。 我们发现，如果我们拿一条斜率为 的直线 去切这个由 点集构成的图像。那么在切点 处，如果我们知道 的截距 ，那么 就可以写做 。那么由于这个 函数是单调的，如果通过斜率可以得到 ，在 处切线的斜率是可以通过二分得到的。 这样我们我们可以通过二分斜率，再从切点的横坐标，再调整斜率来找到横坐标为 时，切线直线的 。那么我们现在的问题就转化为，如何求出一条斜率为 的直线与 的切点和此时 的在 轴上的截距 。那么答案为 。

• 回到原问题，如果我们仔细观察，如果我们把每一段的价值 。那么定义 为 结尾的最小值 ，定义 。那么转移为 。这样我们就去掉了个数 的限制。那么关于上式子可以斜率优化解决，这里不详细展开了（后面有类似例题）。就此我们可以 求出原问题了。

总结

• 我们先分析出函数的单调性，在通过二分斜率，找到切点。最后通过切点横坐标 与答案坐标 调整斜率找到 的答案。
• 二分斜率，一定要记住我们求出的是 的斜率为 是的切点。而在整数二分时，可能有两个切点。这个要看你是如何二分的，最后一定要取横坐标为 时的答案，而不是直接取切点的横坐标。

例题

很遗憾，我并没有找到太多的例题，但大概也有非常好的训练效果。

P4983 忘情

题意

也是分 段，每一段的价值为 最小化价值和。

分析

同上题。式子基本一模一样。那么省去二分斜率这些步骤。我们重点分析一下 这个式子。令 为 的转移点。那么 移项之后 。由于我们要维护 的最小值，所以我们考虑用单调栈维护一个凸壳。然后就是斜率优化的模板了 ，其中 为 ，斜率为 ， 。那么一次 的复杂度就下降到 了。

代码

#include<bits/stdc++.h>
using namespace std;
int read() {
    int x = 0,f = 0;char ch = getchar();
    while(!isdigit(ch)) {if(ch == '-')f = 1;ch = getchar();}
    while(isdigit(ch)) {x = x * 10 + ch - '0';ch = getchar();}
    return f ? -x : x;
} 
#define ll long long
const ll inf = 1e18;
const int N = 1e5 + 100;
ll f[N],g[N],q[N],s[N];
int n,m;
#define Y(a) (f[a]+s[a]*s[a]-2*s[a])
#define X(a) (s[a]) 
long double K(int a,int b) {
    return (long double)(Y(b) - Y(a)) / (X(b) - X(a));
}
void check(ll mid) {
    memset(f,0x3f,sizeof(f));memset(g,0,sizeof(g));
    f[0] = 0;int l = 1,r = 1;
    q[1] = 0;
    for(int i = 1;i <= n;i++) {
        while(l < r && K(q[l],q[l + 1]) < 2 * s[i]) l++;
        f[i] = f[q[l]] + (s[i] - s[q[l]] + 1) * (s[i] - s[q[l]] + 1) + mid;
        g[i] = g[q[l]] + 1;
        while(l < r && K(q[r - 1],q[r]) > K(q[r - 1],i)) r--;
        q[++r] = i;
    }
}
int main() {
    n = read();m = read();
    for(int i = 1;i <= n;i++) s[i] = s[i - 1] + read();
    ll l = 0,r = inf,ans = 0;
    while(l <= r) {
        ll mid = l + r >> 1;check(mid);
//        cout << g[n] << endl;
        if(g[n] <= m) ans = mid , r = mid - 1;
        else l = mid + 1;    
    }
    check(ans);
    printf("%lld\n",f[n] - m * ans);
    return 0;
}

[国家集训队2]Tree I

分析

我们令 为选择 条白边的最小生成树的代价。根据直觉的分析，在某一个位置 前时，我们选择白边比黑边要优，是一个逐渐增加，斜率逐渐减小的函数。而 后面选择黑边要优，是一个斜率的增加，值不断减小的函数。那么我们给白色的边加上一个权值 ，在这个情况下做最小生成树。最后返回使用的白色边的个数和最小生成树的代价。那么二分完 之后，最后的答案为 。总的复杂度为 。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e5 + 1000;
struct Edge {ll x,y,w,col;}e[N];
int read() {int x;scanf("%d",&x);return x;}
ll n,m,k,tot = 0,Ans = 0,f[N];
bool cmp(Edge x,Edge y) {return (x.w < y.w) || (x.w == y.w && x.col > y.col) ;}
ll find(ll x) {return f[x] == x ? x : f[x] = find(f[x]);}
void MST(ll mid) {
    tot = 0;Ans = 0;
    for(int i = 1;i <= m;i++) if(e[i].col) e[i].w += mid;
    for(int i = 1;i <= n;i++) f[i] = i;
    sort(e + 1,e + 1 + m,cmp);
    for(int i = 1;i <= m;i++) {
        int x = find(e[i].x),y = find(e[i].y);
        if(find(x) == find(y)) continue;
        Ans += e[i].w;tot += e[i].col;
        f[find(x)] = find(y);
    }
    for(int i = 1;i <= m;i++) if(e[i].col) e[i].w -= mid;
}
int main() {
    n = read();m = read();k = read();
    for(int i = 1;i <= m;i++) {
        e[i].x = read() + 1;e[i].y = read() + 1;
        e[i].w = read();e[i].col = 1 - read();
    }
    ll l = -1e9,r = 1e9,ans = 0;
    while(l <= r) {
        ll mid = l + r >> 1;
        MST(mid);
        if(tot >= k) ans = mid,l = mid + 1;
        else r = mid - 1;
    }
    MST(ans);
    printf("%lld\n",Ans - k * ans);
    return 0;
}

剩下的例题

• P4383 [八省联考2018]林克卡特树 代码
• CF739E Gosha is hunting 代码
• P4767 [IOI2000]邮局 代码

最后的话

• 常见问法，强制规定只能选 个物品，问最优答案。

• 一定要注意切点不止一个，在整数二分时。