专栏文章

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

WWaterSun/cy
P10260题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mip1hr78
此快照首次捕获于
2025/12/03 04:37
3 个月前
此快照最后确认于
2025/12/03 04:37
3 个月前
查看原文
更好的阅读体验
信息学不是数学，所以乐子题解当乐子看看就行了 /lh

思路

大胆猜测，当查询的 hh 变小时，用按钮的次数一定不会减少，于是上决策单调性可以直接秒掉。
接下来尝试证明一下。设允许的最高高度为 hh，令 f(x)f(x) 表示按 xx 次按钮的代价，g(h,x)g(h,x) 表示按 xx 次后还需要单独操作的贡献以达到 hh，则当询问 hh 时先按 xx 次按钮的代价就是 c(h,x)=f(x)+g(h,x)c(h,x) = f(x) + g(h,x)。
把 f(x),g(h,x)f(x),g(h,x) 表示出来，其中 cnticnt_i 表示 aa 中 ≤i\leq i 的元素数量，sumisum_i 表示 aa 中 ≥i\geq i 的元素之和，sis_i 表示 aa 中 =i= i 的元素之和，viv_i 表示 aa 中 =i= i 的元素数量：
f(x)=f(x−1)+s+k×cntx−1g(h,x)=(sumh+x+1−(cntm−cnth+x)×(x+h))×tf(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) 与 c(h,x+1)c(h,x + 1) 的增量 Δc(h,x)\Delta c(h,x)：
Δc(h,x)=Δf(h,x)+Δg(h,x)=s+k×cntx−1+(vh+x+1−sh+x+1)×t\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
显然 Δc(h,x)\Delta c(h,x) 随 hh 的增大而减小，且 c(h,x)c(h,x) 是一个单谷函数。我们希望对于每一个询问每一次选择的 c(h,x)c(h,x) 都尽量的小，因此我们的决策点 pp 一定为最小的满足 Δc(h,x)≥0\Delta c(h,x) \geq 0 的数。
由于 Δc(h,x)\Delta c(h,x) 单调递减，因此对于一个较大的 hh 其决策点 pp 一定较小。于是满足决策单调性的定义，证毕！

Code

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...