专栏文章

题解：P2048 [NOI2010] 超级钢琴【思维贪心+数据结构】

yylch
P2048题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mio2jzvx
此快照首次捕获于
2025/12/02 12:19
3 个月前
此快照最后确认于
2025/12/02 12:19
3 个月前
查看原文
发现区间不定长，这就很讨厌。

暴力

考虑对于每个以 ii 为左端点的区间，因为长度范围 [L,R][L,R]，所以右端点范围为 [i+L−1,i+R−1][i+L-1,i+R-1]。
不难想到区间和可以用前缀和数组 ss 来快速取得。
考虑暴力存储所有的区间和再排序，时间复杂度可以达到 O(n2log⁡n)O(n^2 \log n)。

正解

书接上回，考虑对于每个以 ii 为左端点的区间，如果只取一次，那么它能取到的最大值应该是 max⁡{s[x]}−s[i−1], x∈[i+l−1,i+r−1]\max\{s[x]\} - s[i-1],\ x \in [i+l-1,i+r-1]。发现每个 s[x]s[x] 都必须减去 s[i−1]s[i-1]，那么比大小就成了纯比较 s[x]s[x]。不难想到可以用 ST 表维护任意区间中的最大前缀和以及位置（代码实现得很妙）。
现在我们能快速取得最值信息了，下面就思考贪心策略：怎样取最优？
首先对于最大美妙度，如果把之前预处理出来的每个 ii 的信息都放到大根堆里，那么排序后堆顶肯定就是最大的。
那第二大呢？我们可以破开最大的，假设最大值的前缀和为 sts_t，将原本的 [i,t][i,t] 删掉，再把 [i,(i+L−1)∼(t−1)][i,(i+L-1) \sim (t-1)] 和 [i,(w+1)∼(i+R−1)][i, (w+1) \sim (i+R-1)] 中的最大值入堆。
破开依据：“两个超级和弦被认为是相同的，当且仅当这两个超级和弦所包含的音符集合是相同的”。
那这样贪心为什么是对的呢？好像很显然。 因为一个 ii 为左端点的最大值摘出去后，ii 可能还会作为其他有用值的左端点，所以再放回去就很对。
这样就解决了，考虑把状态 (i,l,r,t)(i,l,r,t) 表示左端点为 ii，右端点可以在 [l,r][l,r] 范围内，前缀和最大值的下标为 tt。
O(nlog⁡n)O(n \log n)。
这种问题的通法：建立集合 SS，使当前剩余最大值一定存在于 SS 中，且使得将最大值排除后，集合性质不变。
CPP
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e5 + 7;

int n, k, L, R, st[maxn][30]; // 这里的st中存的是最大前缀和的下标
ll s[maxn];

void init(){
    for(int i = 1; i <= n; i ++) st[i][0] = i;
    for(int j = 1; j <= log2(n); j ++){
        for(int i = 1; i + (1 << j) - 1 <= n; i ++){
            int a = st[i][j - 1], b = st[i + (1 << (j - 1))][j - 1];
            st[i][j] = s[a] > s[b]? a : b; // 比较值的大小，存下标即可
        }
    }
}
int query(int l, int r){
    int k = log2(r - l + 1);
    int a = st[l][k], b = st[r - (1 << k) + 1][k];
    return s[a] > s[b]? a : b;
}

struct Node{
    int i, l, r, t;
    bool operator < (Node p) const{
        return s[t] - s[i - 1] < s[p.t] - s[p.i - 1]; // 注意堆默认大顶堆，这里重载是小于号，排序规则反过来
    }
};
priority_queue<Node> Q;

void solve(){
    cin >> n >> k >> L >> R;
    for(int i = 1; i <= n; i ++){
        cin >> s[i]; s[i] += s[i - 1]; // 直接输入前缀和数组即可
    }
    init();
    for(int i = 1; i + L - 1 <= n; i ++){
        int l = i + L - 1, r = min(n, i + R - 1);
        Q.push({i, l, r, query(l, r)});
    }
    ll ans = 0;
    while(k --){
        auto [i, l, r, t] = Q.top(); Q.pop();
        ans += s[t] - s[i - 1];
        if(l != t) Q.push({i, l, t - 1, query(l, t - 1)});
        if(r != t) Q.push({i, t + 1, r, query(t + 1, r)}); // 破开当前元素，重新放入堆中
    }
    cout << ans << '\n';
}

signed main(){
    ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
    return 0;
}

评论

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

正在加载评论...