P6246 [IOI2000] 邮局加强版

aaaaaaaawsl · 2023-07-31 18:01:55 · 题解

推荐预先食用：P4767 [IOI2000] 邮局。

前置知识：wqs 二分，推销本人的博客。

那么本题，用四边形不等式优化的做法是 O(nm) 的，面对 n, m 都 5 \times 10^5 的数据显然过不去，考虑换种优化。

考虑朴素 DP：设 f_{i,k} 为考虑到第 i 位，分了 k 段的答案。

下面观察题面，明显的有必须要建立 m 个邮站，这符合 wqs 二分处理的问题的恰好选择 m 件物品的特性（详情见博客）。所以尝试使用 wqs 二分优化掉第二维。

决策单调性由普通版本的四边形不等式的推导过程可以轻松得出，这里感性理解下凸性：

对于 f_k 表示分 k 段的最优价值，我们总可以取出某一段，将他再分成两段，使得 f_{k - 1} \le f_{k} 分段优化的价值和段内村庄数正相关，随着分段的增多，段内的村庄数下降，优化的价值下降，所以函数成上凸。

对此，可以二分斜率，O(n) DP 维护即可。时间复杂度 O(n\log m)。

对于每一次 DP 中，由于决策单调性，用一个队列维护决策点，如果该决策点的管辖范围小于当前枚举的点，就从队首弹出，如果队尾决策点被次队尾决策点和当前决策点的范围覆盖，那么从队尾弹出。

下面是实现的一些细节。

要尤其注意二分的写法，因为本题可能存在共线情况，由于函数单调不增，所以二分尽可能选右侧的点。以及二分边界等等（在二分上错了十几版）。
预处理前缀和以做到 O(1) 求出两个点之间放一个邮局的最优价值。
注意边界和判断条件中的等号是否添加。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long

using namespace std;

inline int read(){
    register int x = 0, f = 1; register char ch = getchar();
    for(; ch > '9' || ch < '0'; ch = getchar()) if(ch == '-') f = -1;
    for(; ch >= '0' && ch <= '9'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
    return x * f;
}

const int N = 5e5 + 10;

int n, m, ans;
int a[N], sum[N];
struct node{
    int pos, r;
}q[N];
struct Node{
    int val, x;
}f[N];

int calc(int l, int r){
    l += 1;
    int mid = (l + r) >> 1;
    int ans = 1ll * (sum[r] - sum[mid]) - (1ll * a[mid] * (r - mid)) + (1ll * a[mid] * (mid - l)) - (sum[mid - 1] - sum[l - 1]);
    return ans;
}

int find(int i, int j){
    int l = j, r = n + 1;
    while(l < r - 1){
        int mid = (l + r) >> 1;
        if(f[i].val + calc(i, mid) < f[j].val + calc(j, mid)) l = mid; 
        else r = mid;
    }
    return r;
}

//int find(int i, int j){
//  int l = j, r = n + 1, p;
//  while(l <= r){
//      int mid = (l + r) >> 1;
//      if(f[i].val + calc(i, mid) < f[j].val + calc(j, mid)) l = mid + 1, p = mid; 
//      else r = mid - 1;
//  }
//  return p;
//}

//int find(int i, int j){
//  int l = j, r = n + 1, mid;
//  while(l < r){
//      mid = (l + r + 1) >> 1;
//      if(f[i].val + calc(i, mid) <= f[j].val + calc(j, mid)) l = mid; 
//      else r = mid - 1;
//  }
//  return mid;
//}

int check(int mid){
    int hh = 1, tt = 0;
    q[++ tt].pos = 0; q[tt].r = n + 1;
    for(int i = 1; i <= n; ++ i){
        while(hh < tt && q[hh].r <= i) hh ++;
        f[i].val = f[q[hh].pos].val + calc(q[hh].pos, i) - mid;
        f[i].x = f[q[hh].pos].x + 1;
        while(hh < tt && find(q[tt].pos, i) <= q[tt - 1].r) tt --;
        q[tt].r = find(q[tt].pos, i);
        q[++ tt].r = n + 1; q[tt].pos = i;
    }
    return f[n].x;
}


signed main(){
    n = read(); m = read();
    for(int i = 1; i <= n; ++ i) a[i] = read();
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++ i)sum[i] = sum[i - 1] + a[i];
    int l = -5e11, r = 0, p;
    while(l <= r){
        int mid = (l + r) >> 1;
        if(check(mid) <= m) l = mid + 1;
        else r = mid - 1, p = mid;
    }
    check(p);
    printf("%lld", f[n].val + p * m);
    return 0;
}

P6246 [IOI2000] 邮局 加强版

Code

P6246 [IOI2000] 邮局加强版