[题解]P10260 [COCI 2023/2024 #5] Rolete

· · 题解

更好的阅读体验

信息学不是数学，所以乐子题解当乐子看看就行了 /lh

思路

大胆猜测，当查询的 h 变小时，用按钮的次数一定不会减少，于是上决策单调性可以直接秒掉。

接下来尝试证明一下。设允许的最高高度为 h，令 f(x) 表示按 x 次按钮的代价，g(h,x) 表示按 x 次后还需要单独操作的贡献以达到 h，则当询问 h 时先按 x 次按钮的代价就是 c(h,x) = f(x) + g(h,x)。

把 f(x),g(h,x) 表示出来，其中 cnt_i 表示 a 中 \leq i 的元素数量，sum_i 表示 a 中 \geq i 的元素之和，s_i 表示 a 中 = i 的元素之和，v_i 表示 a 中 = i 的元素数量：

f(x) = f(x - 1) + s + k \times cnt_{x - 1}\\ g(h,x) = (sum_{h + x + 1} - (cnt_m - cnt_{h + x}) \times (x + h)) \times t

考虑 c(h,x) 与 c(h,x + 1) 的增量 \Delta c(h,x)：

\Delta c(h,x) = \Delta f(h,x) + \Delta g(h,x) = s + k \times cnt_{x - 1} + (v_{h + x + 1} - s_{h + x + 1}) \times t

显然 \Delta c(h,x) 随 h 的增大而减小，且 c(h,x) 是一个单谷函数。我们希望对于每一个询问每一次选择的 c(h,x) 都尽量的小，因此我们的决策点 p 一定为最小的满足 \Delta c(h,x) \geq 0 的数。

由于 \Delta c(h,x) 单调递减，因此对于一个较大的 h 其决策点 p 一定较小。于是满足决策单调性的定义，证毕！

Code

#include <bits/stdc++.h>
#define re register
#define int long long

using namespace std;

const int N = 2e5 + 10;
const int inf = (int)(1e18) + 10;
int n,t,s,k,q,m;
int arr[N],cnt[N],sum[N],cst[N],ans[N];

inline int read(){
    int r = 0,w = 1;
    char c = getchar();
    while (c < '0' || c > '9'){
        if (c == '-') w = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9'){
        r = (r << 3) + (r << 1) + (c ^ 48);
        c = getchar();
    }
    return r * w;
}

inline void dfs(int l,int r,int vl,int vr){
    if (l > r) return;
    int mid = l + r >> 1;
    int Min = inf,pos = 0;
    for (re int i = vl;i <= vr;i++){
        int val = cst[i] + (sum[mid + i + 1] - (cnt[m] - cnt[mid + i]) * (i + mid)) * t;
        if (Min > val) Min = val,pos = i;
    } ans[mid] = Min;
    dfs(l,mid - 1,pos,vr); dfs(mid + 1,r,vl,pos);
}

signed main(){
    n = read(),t = read(),s = read(),k = read();
    for (re int i = 1;i <= n;i++){
        cnt[arr[i] = read()]++; sum[arr[i]] += arr[i];
    } m = *max_element(arr + 1,arr + n + 1);
    for (re int i = 1;i <= 2 * m;i++) cnt[i] += cnt[i - 1];
    for (re int i = m;~i;i--) sum[i] += sum[i + 1];
    for (re int i = 1;i <= m;i++) cst[i] = cst[i - 1] + s + k * cnt[i - 1];
    dfs(0,m,0,m); q = read();
    while (q--) printf("%lld ",ans[read()]);
    return 0;
}