题解：P17319 [ICPC 2018 Nanjing R] Tournament

lailai0916 · 2026-08-31 08:09:22 · 题解

题意简述

数轴上有 n 户村民，需要修建 k 个体育场。每户村民前往最近体育场，求最小距离总和。

解题思路

先把每户村民分配给离它最近的体育场。沿数轴从左向右观察，分配给同一体育场的村民可以取成连续一段。否则，把两段交错的归属在分界处交换，不会增加任何人的路程。

所以只需把有序坐标划分为 k 个非空连续段。每段独立选择一个体育场位置。绝对值之和在中位数处最小。对于区间 [l,r]，可取 m=\lfloor(l+r)/2\rfloor，并把体育场建在 a_m。

设前缀和为 s_i=\sum_{j=1}^ia_j，m=\lfloor(l+r)/2\rfloor。区间只修建一个体育场的代价为：

设 F_{i,t} 为前 i 户村民使用 t 个体育场的最小代价，直接转移为：

该动态规划有 O(nk) 个状态，仍然无法通过。给每个新段附加整数代价 c，便可用 WQS 二分消去段数这一维。

令 f_i 为前 i 户村民的最小带权代价。令 g_i 为达到该代价时的最大段数，则：

接下来需要快速完成一次带权动态规划。固定左端点 l，把右端点从 r 扩展到 r+1，代价增量为：

若把左端点右移，中位数下标不会减小。坐标已经有序，所以这个增量不会增大。这正是 w 的四边形不等式，也给出了转移的决策单调性。

具体地，考虑两个分界点 x<y。当右端点增长时，较新的决策 y 相对 x 的优势单调不减。因此，一旦 y 在某个右端点不劣于 x，它在此后的所有位置都不会变劣。两者的负责范围至多在一个位置发生切换。

从左向右计算 f_i，并维护若干三元组 (p,l,r)。它表示在当前已经出现的分界点中，p 是右端点区间 [l,r] 的最优决策。所有区间按顺序首尾相接，故当前位置直接使用队首决策。

计算完 f_i 后，分界点 i 会成为新决策。若它在队尾区间左端已经更优，决策单调性说明它支配整个队尾，可直接删除该区间。重复删除后，若它在最后一个位置仍不更优，则它永远不会进入最优解；否则在剩余队尾中二分首个胜出位置，切开旧区间并把新区间接到末尾。

每个决策只会入队一次、出队一次。插入一个决策至多进行一次二分，所以一次检查的时间复杂度为 O(n\log n)。

比较两个决策时，先比较带权代价。代价相同时选择段数更多的决策，使 g_n 表示所有最优方案中的最大段数。随着 c 增大，g_n 单调不增。

二分最大的整数 c，使 g_n\ge k。上界取 w(1,n)+1，此时使用一段严格优于使用更多段。最终答案为 f_n-ck。

一次检查为 O(n\log n)，WQS 二分进行 O(\log(na_n)) 次。总时间复杂度为 O(n\log n\log(na_n))，空间复杂度为 O(n)。

正确性证明

先证明分段模型等价于原问题。任意两个体育场的最近点分界只有一个，距离相同的村民可以归入任意一侧。因此，每个体育场负责的村民可以取成连续区间。反过来，可在每个连续分段的中位数处建体育场。产生的代价恰为各段 w(l,r) 之和。

再证明固定 c 时的决策队列正确。w 的右端增量关于左端点单调。对任意旧决策 x<y，y 只可能在某个后缀不劣于 x。两者不会反复交换优劣。

假设加入新决策前，队列区间恰好覆盖全部尚未计算的位置，并记录每个位置的最优决策。删除队尾时，新决策已在该区间左端胜出，故它支配整个区间。删除停止后，新决策若能胜出，范围必为最后一个区间的后缀；二分得到其左端即可保持覆盖与最优性两个不变式。

初始时只有分界点 0，它负责全部右端点。结合上述插入过程归纳可知，队首决策始终给出当前 f_i。比较决策时若代价相同便选择段数更多者，因此还能得到带权最优方案中的最大段数 g_i。

最后证明 WQS 二分恢复恰好 k 段的答案。设 A_t 为恰好划分成 t 段的最小原代价。四边形不等式保证序列 A_t 离散凸。固定 c 时，动态规划求得：

在相同最小值中取最大的 t 后，最优段数随 c 单调不增。取最大的整数 c，使最优段数仍不小于 k。离散凸函数在该斜率处必然包含下标 k 的最优点。因此 A_k=f_n-ck。

综上，算法输出的就是修建 k 个体育场时的最小交通代价。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=300005;
struct seg
{
    int x,l,r;
};
int n,k;
int a[N],g[N];
ll s[N],f[N];
seg q[N];
ll w(int l,int r)
{
    int m=(l+r)>>1;
    return (ll)a[m]*(m-l+1)-s[m]+s[l-1]+s[r]-s[m]-(ll)a[m]*(r-m);
}
bool better(int x,int y,int i,ll c)
{
    ll u=f[x]+w(x+1,i)+c,v=f[y]+w(y+1,i)+c;
    return u!=v?u<v:g[x]>g[y];
}
void add(int x,ll c,int &h,int &t)
{
    while(h<=t&&better(x,q[t].x,q[t].l,c))t--;
    if(h>t)
    {
        q[++t]={x,x+1,n};
        return;
    }
    if(!better(x,q[t].x,n,c))return;
    int l=q[t].l,r=n;
    while(l<r)
    {
        int m=(l+r)>>1;
        if(better(x,q[t].x,m,c))r=m;
        else l=m+1;
    }
    q[t].r=l-1;
    q[++t]={x,l,n};
}
int check(ll c)
{
    f[0]=0;
    g[0]=0;
    int h=0,t=0;
    q[0]={0,1,n};
    for(int i=1;i<=n;i++)
    {
        while(q[h].r<i)h++;
        int x=q[h].x;
        f[i]=f[x]+w(x+1,i)+c;
        g[i]=g[x]+1;
        if(i==n)break;
        q[h].l=i+1;
        if(q[h].l>q[h].r)h++;
        add(i,c,h,t);
    }
    return g[n];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        s[i]=s[i-1]+a[i];
    }
    ll l=0,r=w(1,n)+1;
    while(l<r)
    {
        ll m=(l+r+1)>>1;
        if(check(m)>=k)l=m;
        else r=m-1;
    }
    check(l);
    cout<<f[n]-l*k<<'\n';
    return 0;
}